Questions tagged [turing-recognizable]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
22 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
59 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
1 vote
93 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 ...
57 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 ...
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
58 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 ...
36 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. ...
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 ...
52 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
167 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
60 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
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}. ...
94 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 ...
• 80
73 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,710
1 vote
313 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
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
113 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?
343 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
67 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
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
50 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
162 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
154 views

• 55
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
615 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