Skip to main content

Questions tagged [turing-recognizable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
45 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 ...
user5507's user avatar
  • 2,191
4 votes
1 answer
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 ...
Ben I.'s user avatar
  • 1,710
3 votes
1 answer
126 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 ...
HappyFace's user avatar
  • 211
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 ...
Aditya 's user avatar
  • 123
1 vote
3 answers
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 ...
Mika Li's user avatar
  • 11
1 vote
2 answers
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 ...
Muhammad Zulqarnain Malik's user avatar
1 vote
1 answer
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 ...
Luis Ramirez's user avatar
1 vote
2 answers
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 ...
jcora's user avatar
  • 125
1 vote
1 answer
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 ...
lz9866's user avatar
  • 315
1 vote
1 answer
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 ...
sadia's user avatar
  • 11
1 vote
1 answer
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. ...
RookieCookie's user avatar
1 vote
2 answers
143 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}...
PedrV's user avatar
  • 55
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 ...
Pietro's user avatar
  • 316
0 votes
1 answer
154 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,\...
sockaddr's user avatar
0 votes
1 answer
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 ...
Mark's user avatar
  • 1
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 ...
Dilfira Kudrat's user avatar
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}. ...
AAAAA5555555's user avatar
0 votes
1 answer
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 ...
lz9866's user avatar
  • 315
0 votes
1 answer
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
lz9866's user avatar
  • 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 ...
lz9866's user avatar
  • 315
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 ...
paulMarty 's user avatar
0 votes
0 answers
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-...
Jane's user avatar
  • 1
0 votes
0 answers
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 ...
Javier's user avatar
  • 1
0 votes
1 answer
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. ...
Arthur's user avatar
  • 3
0 votes
1 answer
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 ...
John's user avatar
  • 1
0 votes
1 answer
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 ...
revision's user avatar
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?
Sam333's user avatar
  • 109
0 votes
1 answer
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 ...
Geo's user avatar
  • 47
0 votes
1 answer
107 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 ...
StudentDegree's user avatar
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 ...
Miguel JV's user avatar
-1 votes
1 answer
83 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 ...
DRE's user avatar
  • 121
-1 votes
2 answers
198 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 ...
bireugit's user avatar
-2 votes
1 answer
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?
Tomer Mor's user avatar