Questions tagged [turing-recognizable]
The turing-recognizable tag has no usage guidance.
39
questions
1
vote
1
answer
238
views
Is UNIQUE(N) Turing-recognizable?
Let N be a non-deterministic TM with Σ as its alphabet, and we define the next language:
UNIQUE(N) = {w∈Σ*|w has an unique accepting path on N}.
w can have another computational paths on M, but none ...
- 141
1
vote
1
answer
102
views
result of a union between a decidable language and not recognizable one - disjoint
I have two infinite languages, A and B, and they're disjoint.
A is not Turing recognizable, and B is decidable.
What's the result of their union? meaning, is it a decidable/recognizable/not ...
- 141
0
votes
1
answer
47
views
The number of words that M doesn't accept is finite
I need to show that the following language isn't Turing recognizable:
$$\text{COFINITE}_{TM} = \{\langle M \rangle | M \text{ is a TM and } \overline{L(M)} \text{ is a finite language}\}$$
but I keep ...
- 141
1
vote
1
answer
98
views
set of words w such that M halts on w is decidable
I need to prove that the language following language is not turing-recognizable:
$$\text{dec-haltTM} = \{ \langle M\rangle: \text{$M$ is a TM and the set of words that M halts on is decidable}\}$$
I ...
- 141
1
vote
1
answer
57
views
$L=\left \{ \left \langle M,D \right \rangle : M=TM\, ,\, D=DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}\notin RE$
$L=\left \{ \left \langle M,D \right \rangle : M\, is\, a\, TM\, ,\, D\, is\, a\, DFA\, ,\, L(D)\neq \emptyset\, ,\, L(M)\subseteq L(D)\circ L(D) \right \}$
$L\notin R$ which can be shown for example ...
- 185
1
vote
2
answers
48
views
Rice theorem - $EQ_{TM}$
Could use some help understanding if Rice’s theorem applies to the following language: $𝐿 = \{\langle 𝑀\rangle \lvert M \text{ 𝑖𝑠 𝑎 𝑇𝑀 𝑎𝑛𝑑 } 𝐿(𝑀) \subseteq 𝐸𝑄_{TM} \}$ (where $EQ_{TM} =\{...
- 73
0
votes
0
answers
24
views
Prove that the complement of the language L = { <T> : T is a Turing machine that runs in polynomial time } is not turing recognizable
To show that L is not Turing-recognizable, we can use a reduction from the complement of the ATM problem (ATM'). However, I'm not sure about how we would prove that the complement of L is not Turing-...
- 1
0
votes
1
answer
61
views
If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?
"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A ...
- 1
2
votes
2
answers
145
views
How to write a turing machine program for any given problem?
I'm learning about Turing machine program,i want to know how we write a Turing machine program about any given problem, like a string is accepted by Turing machine, program (for a Single Tape Turing ...
0
votes
0
answers
65
views
Multitape Turing Machine to accept power of 2 length 0's string?
I have been trying to find a multitape Turing Machine in order to accept a input string which consists on 0's and whose length is a power of 2:
However, Im getting troubble finding it, because I dont ...
- 1
2
votes
1
answer
55
views
Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?
I am asking this in the context of the following question:
Let N be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where ...
- 123
1
vote
1
answer
59
views
If A U B and A ∩ B are recognizable, then is one of A, A', B, B' also recognizable?
I know that if decidability of $A \cap B$ and $A \cup B$ doesn’t
guarantee the decidability of any of $A$ or $B$. We can prove that:
ATM is not decidable. Since decidable languages are closed under ...
- 11
0
votes
1
answer
37
views
Can an unreocognizable language be Turing-reducible to a recognizable language?
Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable?
With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
- 3
0
votes
1
answer
59
views
Is there any example of a Turing-recognizable language mapping reducible to a NOT Turing-recognizable language?
Theorem: "If A is mapping reducible to B and B is recognizable, then A is recognizable."
I know that the following statement is FALSE.
"If A is mapping reducible to B and A is ...
0
votes
1
answer
57
views
Reduction from a language with unknown decidability to HALT
We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction
$$
L\leq_mHALT
$$
So that I can ...
- 1
1
vote
1
answer
195
views
Proving that $Prefix(L)$ is recursively enumerable
Given a language $L$ that is recursive prove that $Prefix(L) = \{ x \ | \ xv \in L\}$ is recursively enumerable.
My first attempt at this was to try and formulate an algorithm in pseudocode.
...
- 165
1
vote
3
answers
62
views
turing recognisable = complement of co-recognisable
Define: RE = {L : L is recognizable by a TM}, R = {L : L is decidable by a TM}, and
coRE = {L : L-complement is recognizable by a TM}.
The question is: Does the complement of coRE equal RE?
I know ...
- 11
0
votes
1
answer
28
views
is this lanuage or it' complement not Turing-recognisable
K = {<J, a, b, c> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}.
...
- 29
0
votes
1
answer
97
views
Proving a language is recursively enumerable
Prove that the following language is recursively enumerable:
L = {<M,x> | Turing machine M enters the same configuration twice on input x}
I have tried to construct a TM that maintains the ...
- 90
4
votes
1
answer
78
views
Simple, intuitive example of non recursively enumerable languages
This question is a bit of a shot in the dark. I am asking here, though I am not convinced that such an example exists.
I'd like a quick, highly intuitive example that I can throw out to my students ...
- 1,720
1
vote
2
answers
350
views
Prove that the language L = { <T> : T is a Turing machine that runs in polynomial time } is not Turing-recognizeable
By "$T$ runs in polynomial time", I mean that $T$ halts for every input of length $n$ in $O(n^k)$ steps for some $k$.
By Turing-recognizable, I mean that there exists a Turing machine that ...
- 125
0
votes
0
answers
28
views
Is this language recognizable or unrecognizable
Let L = { y = {0,1}* | y = code(M) for some Turing Machine M and M halts on no input}
How can I prove whether this language recognizable or unrecognizable?
- 109
-2
votes
1
answer
153
views
EPSILON(CFG) = {<G,H> | G and H are CFGs where the concatenation is epsilon. is this language Turing-recognizable?
It is given that the language is not decidable.
Is this language Turing-recognizable?
0
votes
1
answer
373
views
If a language is undecidable, then its complementary language must also be undecidable?
Reference from here If a Language is Non-Recognizable then what about its complement?
There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
- 315
0
votes
1
answer
71
views
Unrecognizable languages must be undecidable?
A decidable language must be recognizable.
Unrecognizable languages must be undecidable?
I want to know more about the relation of undecidability and unrecognizability
- 315
0
votes
1
answer
34
views
If the complementary language of an recognizable language is a non-recognizable language, is the recognizable language a non-decidable language?
The complementary language of a recognizable undecidable language is not recognizable.
If the complementary language of an recognizable language is a non-recognizable language, is the recognizable ...
- 315
0
votes
1
answer
57
views
If $B \in RE$ then $A \in RE$ - Reduction
I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$.
I also know that Turing Reduction is for Decision, and not Recognition.
Is it possible to ...
- 47
1
vote
1
answer
166
views
L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?
If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects
However, my question is that
If $L$ is a ...
- 315
0
votes
1
answer
159
views
What is wrong with this proof that shows every language over $\Sigma=\{0, 1\}$ is recognizable?
In the following let $\Sigma=\{0, 1\}$. I'll prove that every language over $\Sigma$ is recognizable.
Let $L\subseteq\Sigma^*$. Let $w_1,w_2,\ldots$ be the list of words in $L$. For every $i=1,2,\...
- 15
1
vote
2
answers
139
views
Languages and Turing Machine
Since strings are finite by definition, then it follows that languages are enumerable because they are finite string sets and we know that finite string sets are enumerable. Turing Machines are ...
0
votes
2
answers
1k
views
Is the union of a Turing-recognisable language and a Turing-decidable language Turing decidable? Is it recognisable?
I was studying Turing languages for an exam and I came up with this problem for wich I haven't found a solution online. This is my question:
Let's say we have $L_1, L_2 \subseteq\{0,1\}^*$. $L_1$ is
...
- 316
-1
votes
1
answer
86
views
If A is Turing-reducible to B and B is Turing recognizable then A is Turing recognizable
I believe this is true and I have given a simple proof of this:
If A is Turing-reducible to B then there exists a Turing machine with oracle for B that decides A, because B is Turing-recognizable then ...
- 121
0
votes
0
answers
12
views
A finite language of chains is TM decidable? [duplicate]
In class we were talking about the decidability and acceptability of languages by Turing Machines but a doubt arose in my mind, "is any language containing a finite number of strings decidable by ...
3
votes
1
answer
128
views
What are some examples of non-enumerable languages whose complement isn't either?
What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.
Update: Found ...
- 211
-1
votes
2
answers
209
views
How to show that language is Turing-recognizable and Turing-decidable?
How do I being to show that if $L_{1}$ is Turing-recognizable language over $\Sigma=\{0,1\}$, then $L_{2} = \{ww^R | w ∈ L_{1} \}$ is a Turing recognizable language too.
There is another similar ...
- 1
1
vote
2
answers
145
views
Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string
I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem.
Let $L_{u}= \{\langle M,w\rangle \mid M\text{ accept }w\}$, $\overline{L_{u}...
- 55
0
votes
1
answer
50
views
Turing recognizability and Reduction Mapping on pairs of related Turing machines
I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on.
Let us call 2 Turing machines related if there
is an input $w$ on which ...
1
vote
1
answer
627
views
Is complement of equality problem of Turing machines Turing-recognizable?
Complement of equality problem of Turing machines is unrecognizable or not-recognizable but How? As per my knowledge it is recognizable if you can decide its accept condition but not reject condition ...
- 11
46
votes
2
answers
22k
views
How to show that a function is not computable? How to show a language is not computably enumerable?
I know that there exists a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
- 2,211