5
votes
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
5
votes
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 ...
D.W.♦
- 141k
4
votes
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
3
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
How to determine whether this language is regular?
For $x = (x_1, \dots, x_n) \in \{0,1\}^n$, define $C_x = \{ w \in \Sigma^* \mid \forall i=1,\dots,n, \;\; \#_{\sigma_i}(w) \equiv x_i \pmod{2} \}$. Notice that the collection $\mathcal{C} = \{C_x \mid ...
- 23.4k
2
votes
Accepted
A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function
"If $L$ is the image of some strictly increasing computable function there's a 1-1 correspondence between the natural numbers and the words in $L$". This is a key observation. You might have ...
- 34k
2
votes
Accepted
Useless states in a PDA
Your formulation of the language is wrong. Your language is a collection of pushdown automata. A PDA $M$ is in your language if it has no useless states. This means that for every state $q$, there is ...
- 270k
2
votes
Accepted
If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?
There is no definitive answer. If predicate $P$ is partially-decidable, $\neg P$ can be decidable, partially-decidable or undecidable.
Let $P(n)$ be "is $n>1$?". $P$ is partially ...
- 34k
2
votes
Decidability of a context free Grammar
"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ...
- 11.2k
2
votes
Accepted
Can 3-SAT be recognized in less than exponential time?
This problem stays an open problem (at least using the intuitive definition of "recognizable in poly time" - either running in poly time or looping forever).
Consider there is such a TM that ...
- 10.8k
1
vote
Accepted
Decidability for intersection of context free and regular languages
The first one you have solved correctly. Emptiness of context-free languages is decidable.
For the second,
we can rewrite $\bar L \cap R = \varnothing$ into $R\subseteq L$. This is undecidable (even ...
- 27.6k
1
vote
Accepted
Show that $ Y \subseteq A^*$ is decidable
Let $x \in A^*$ be your input string. We can check that $x \in X$ and, if that is not the case, reject immediately (since we know that $x \not\in X \supseteq Y$).
Now, we know that exists a Turing ...
- 23.4k
1
vote
Prove decidable
No, this proof is not correct. You can't iterate through all inputs $x\in \Sigma^*$ since it would take you "infinite time".
The correct way to do this is to construct the complement of $D$ (...
- 10.8k
1
vote
Accepted
Reduction from undecidability, decidability to decididabilty
If $L_1$ is decidable and $L_2$ is decidable then it is not necessarily true that $L_1 \le_m L_2$. Consider for example any $L_1$ distinct from $\emptyset$ and pick $L_2 = \emptyset$.
In general, if $...
- 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