# Tag Info

### A language is Turing recognizable iff it is a projection of a decidable language

There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., ...
• 20.4k

### Effectively decidable vs. noneffectively (or ineffectively) decidable

"Decidable" and "effectively decidable" mean the same thing. I realize that's a bit confusing; but it reflects a difference in terminology between two communities. (Strictly ...
• 141k
Accepted

### Why REC languages is undecidable under emptiness and finiteness?

To decide whether a language is empty you'd have to run $M$ on all possible input strings and verify that $M$ always rejects. How are you going to do that in a way that ensures that your algorithm ...
• 23.4k
Accepted

### Language of Turing machines that go through some configuration infinitely many times on empty input

No, $L$ is not decidable. Summary (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will ...
• 34k
Accepted

### For any two languages A and B there exists J such that both A and B are Turing reducible to J

I don't think this proposition can be proved using the hierarchy of languages as illustrated in the question alone. That hierarchy of languages is too coarse to imply directly any implication between ...
• 34k
Accepted

### Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Here is the idea in a nutshell: Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \{t\}$, where $t$ is the transcript of the ...
• 270k

### Regularity of CFG and DCFL

Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class. Regularity of the language ...
• 270k

### Regularity of CFG and DCFL

Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement. The ...
• 27.6k
Accepted

### Why finiteness problem of CFL is decidable?

The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$. This is easy to check.
• 13.6k

• 23.4k
1 vote

### Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

I finally understood what was blocking me. We only need a TM that recognizes an undecidable language so we just have to take a TM $M'$ that recognizes $A_{TM}$ for example and return it when $M$ ...
• 31
1 vote

### Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

Maybe try to use Rice' theorem, instead of reducing from $\overline{A_{TM}}$.
• 10.8k
1 vote
Accepted

### Decidability of $\{⟨G⟩ \mid \text{$G$is CFG and$L(G) ⊈ \Sigma^+$}\}$

The idea is that $L(G) \not\subseteq \Sigma^* \setminus \{\epsilon\}$ iff $\epsilon \in L(G)$.
• 270k

Only top scored, non community-wiki answers of a minimum length are eligible