Questions tagged [undecidability]
Questions about problems which cannot be solved by any Turing machine.
894
questions
1
vote
1
answer
61
views
If Halting is not recursive, then why is it that not every set of the form $\{M: \text{M is a Turing machine that does XXX}\}$ is not recursive?
Suppose I wish to find out whether $\{M: \text{M is a Turing machine that does XXX}\}$ is recursive, where $XXX$ can be anything about the Turing machine. I have a bad proof that proves that all such ...
- 13
1
vote
1
answer
40
views
What is the difference between $ L_e$ and $E_{TM} $?
What is the difference between $L_e = \{ \langle M \rangle | L(M) = \emptyset \}$ and
$E_{TM} = \{ \langle M \rangle | \text{M is a turing machine and L(M)} = \emptyset \}$?
$L_e$ is not RE and $E_{...
- 11
3
votes
4
answers
440
views
Undecidable problems in finite graphs
Are there any natural questions in finite graphs (or digraphs) that are undecidable?
- 555
0
votes
1
answer
40
views
Using reducibility to prove a language that accepts $\lambda$ and either loops or accepts other strings is undecidable
I am new to the reduction style of proof so I am hoping to get some help on this problem.
Let $L=\{〈M〉:M$ accepts the empty string and does not reject any string$\}$. Prove $L$ is undecidable.
My ...
- 1
1
vote
2
answers
66
views
Gödel's theorem and machines' power
I was studying AI and when a question came to my mind.
I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, ...
- 111
0
votes
0
answers
21
views
Issues in the proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$
I'm studying reducidability in Sipser Book and watching his videos, but I couldn't fully understand his proof of $A_{TM}$ reducidability to $𝐸_{𝑇𝑀}$ (p. 218, 3rd ed).
Consider this extract:
M1 = “...
0
votes
0
answers
20
views
PCP is undecidable, but seems also NP [duplicate]
I've seen the proof that the Post Correspondence Problem is undecidable -- let's call this the problem of taking a finite collection of tiles with top and bottom labeled by any two strings, and ...
- 367
1
vote
2
answers
43
views
Reduce the problem of CFGs with equal languages to the problem of CFGs generating a palindrome
Consider the problem of, given two CFGs $G_1$ and $G_2$, deciding whether they accept the same language, $L(G_1)=L(G_2)$. Call this problem $EQ_{CFG}$.
Also consider the problem of deciding whether a ...
- 367
0
votes
1
answer
43
views
Decide if some DFA is accepted
Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)}
Show Some(DFA) is decidable.
I produced the following answer and wanted to check if I am correct
T="On input ...
- 1
2
votes
1
answer
33
views
Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand
If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
7
votes
1
answer
124
views
Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?
Let $L$ be a language over an alphabet $\Sigma$ and let
$$ \text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \} $$
$$ \text{MAX}(L) = \{ w \in ...
- 213
0
votes
1
answer
33
views
A decision procedure for PCP
I have read that the Post Correspondence Problem is undecidable. Let's say this is the problem of having a finite set of "dominoes" with a string in the top and another string on the bottom....
- 367
0
votes
1
answer
60
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
2
votes
1
answer
114
views
Is matching pairs sufficient?
Book PDF: https://vishub.org/officedocs/13770.pdf
Pg 253 of book
This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
5
votes
1
answer
329
views
Is every non-recursively-enumerable language RE-hard?
Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard?
It seems like a simple question but I can't find an answer.
I tried to ...
- 151