# Questions tagged [turing-recognizable]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
1 vote
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
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
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
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
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
48 views

• 15
1 vote
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 ...
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
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
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 ...
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
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 vote
145 views

1 vote
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