# Questions tagged [undecidability]

Questions about problems which cannot be solved by any Turing machine.

831 questions
Filter by
Sorted by
Tagged with
27 views

• 161
20 views

### Is it a well-posed question to decide whether a process is deterministic, given that the machine is equipped with a TRNG?

Consider a machine equipped with two input devices: A true random number generator for a fair coin toss, and stdin. I wondered whether it's possible to decide that ...
• 221
45 views

### Turing Machine writes "a" for every input w is undecidable

I have a doubt on my solution of the following: Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all ...
• 121
1 vote
59 views

### Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ $E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$ The standard proof for the undecidability of $E_{TM}$ is given in this ...
• 275
182 views

### Disprove: if L is decidable then Prefix(L) is decidable

The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
• 454
1 vote
28 views

### If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable? I think it is Undecidable since if ¬P holds then P ...
1 vote
33 views

### How to show a language is not recursive, without using reductions?

I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
1 vote
72 views

### Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
• 221
1 vote
194 views

### Undecidability in optimal data compression

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
• 163
67 views

### Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
1 vote
91 views

### Proving Undecidability of this Language

Consider the language $$L = \{\langle M \rangle \mid \text{\exists an input x, where |x|<i, such that M halts on x, but it takes at least j steps} \}$$ where $i$ and $j$ are fixed non-...
43 views

### If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

I should prove or give a counterexample to the above statement. In my opinion, this statement is false but I don't manage to find the right counterexample. My idea was to define $C = Σ^*$ because $Σ^*$...
• 117
128 views

### Halting problem. Decider “recognising itself” in the input? Part 2

This is a "revision" of this question, it contained an error I now see. In a nutshell, I was wondering if in the halting problem proof the decider $D$, after recognising its source code in ...
1 vote
69 views

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

Here is the my attempt: Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings. ...
• 173
1 vote
201 views

### Prove that Turing Machine ever writes a blank symbol over a non blank symbol is undecidable

I have been given the following problem from the book Introduction to the Theory of Computation by Martin Sipser and was wondering if my solution is correct: Determine if a Turing Machine ever writes ...
• 181
479 views

### How to show that the NECESSARY_CFG is Turing-recognizable but undecidable?

I have been given the following problem and was wondering if my solution is correct: Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w$ where $w$ is ...
• 181
140 views

### Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$

This question is part of the undecidable lecture by Jeff Erickson. $$\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\}$$ We should prove that this language is ...
• 21
1 vote
66 views

### Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
• 117
41 views

### Post Correspondence Problem is undecidable

I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a ...
35 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 ...
1 vote
57 views

### Prove Language Is Undeciable Using Diagonalization

I was given the following problem and told it has to be solved using diagonalization. However, I am confused as to why diagonalization would be the solution. Would the answer not be since L is ...