# Questions tagged [undecidability]

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

780 questions
Filter by
Sorted by
Tagged with
105 views

### How can I prove the languages of incompressible words is undecidable?

I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ". The proof is as follows : M' = " On input $n$ Enumerate over all $n$-...
417 views

### Is the halting problem undecidable or unrecognizable? [duplicate]

Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems? I understand that if it is undecidable, then it is also unrecognizable. I have seen ...
354 views

793 views

### Language of TM is Undecidable

why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable? I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
389 views

### Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"/convergence? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? The halting problem: The halting problem is a decision problem about properties of computer programs ...
264 views

### Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?

I found the following question Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following ...
641 views

### Confusion about proof of undecidability of REGULAR TM in Sipser's book [duplicate]

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows : ...
480 views

### Recognizer for decidable language and words it doesn't halt on

Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
397 views

### How to prove that a problem is undecidable by using the Halting problem?

I cannot understand how to reduce the halting problem to a property to show that is undecidable. For example, I have this property of a Turing Machine and I have to prove if it's recursive or not: "...
127 views

### Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?

One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
502 views

### Why are not all recursive languages undecidable?

I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If ...
28 views

### A set that is not recursively enumerable and not (K'≤ A)

Is there a set A such that it's not recursively enumerable and not(K'≤ A) ? where K' is complement of K= {n| φ n (n) halts} Thanks!
49 views

### PCP with commutative alphabet

Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable. Is the following variant also known to be ...