People who code: we want your input. Take the Survey

# Questions tagged [semi-decidability]

Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.

196 questions
Filter by
Sorted by
Tagged with
34 views

### Reduction of Turing-machine language

How to show that the following language is undecidable using reduction on the halting problem? $L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$ When TM ...
44 views

### Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?

The negative answer to decidable = non-contracting grammar? suggests the following question: Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. ...
57 views

### Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order. Then, that language/set is decidable. Because it is trivial ...
31 views

### Decidability of languages with dfa/turing-machines

For any alphabet and any natural number k, a language of strings at least k is decidable. So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has ...
73 views

### How to prove (un)decidability

Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
30 views

### TM with double-infinity tape semi-decides the same languages as classical TM

Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the ...
261 views

### is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in ...
61 views

### Characterization of computationally universal functions

Is it correct to state that $u$ is a universal function if and only if $$\forall f : \text{RE} \quad \exists g : \text{R} \quad \exists h : \text{R} \quad f = h \circ u \circ g$$ where RE is the set ...
237 views

### Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
53 views

### Understanding the union of an undecidable language with a finite or decidable language

I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable. This is confusing me because if $L$ were to be a semi-...
28 views

### Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

I have found two interesting questions regarding the quotient of languages, described as: $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$ The first one is: Let $A$ and $B$ be regular languages, ...
70 views

### How this language belong to R?

Consider the following language $$L= \{ \langle M\rangle | \text{ M is a TM, and L(M)\in coRE} \}$$ I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
80 views

### How to show a language is Partially Decidable?

I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine. I am not posting ...
25 views

### Showing semidecidability without using diagonalization

All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down ...
269 views

### Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{$M$accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
21 views

### Can you build a solver for a language from a solver for its complement?

If you have a solver for an L in NP do you have enough information to build a solver for co-L in Co-NP? Meaning, is there a procedure that can take you from a solver for one to a solver for another?
73 views

### How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?

So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.) Question 1 : Show ...
66 views

### Can you build a solver from a verifier?

Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or ...
55 views

### Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$. My idea: It is co-semi-decidable since as soon as i ...
40 views

### Decidability for $\exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \}$ is recursive or ...
40 views

### k-limited solution for PCP

So there's following problem, that has been bugging me for the last few days: A solution of a PCP $i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
43 views

### How to show that these two disjoint sets $A$ and $B$ exist

I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them... In this case, a set $C$ is said to ...
15 views

### Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?

Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?
98 views

### Show that for every language there exists a harder language

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that: $$A \leq_T B$$ but: $$B \not \leq_T A$$ If it is $A \leq_TB$ and ...
48 views

### Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?

I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable. I would say ...
65 views

### Decide if a string is a member of a language that represents $P$?

For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other ...
102 views

### How to prove semi-decidable = verifiable?

A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y) A language is semi-...
### Semi-decidability of the language $\overline{L_{\epsilon}}$
Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...