# Questions tagged [undecidability]

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

661 questions
Filter by
Sorted by
Tagged with
77 views

### Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
21 views

### Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?

I came up with an algorithm to decide this language, but not sure if it is correct? ...
138 views

### Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is: Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps? I highly assume, that this problem is not decidable because in the worst case ...
40 views

### Undecidability of TMs recognizing a decidable language

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...
69 views

### Doubt regarding Cantor's diagonalization argument [closed]

So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider. I understand the overall argument but have a problem regarding one caveat mentioned in my ...
153 views

### Proving the decidability of whether a CFG generates a particular string or not

Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$. Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
61 views

### Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
165 views

### Reducing the halting problem for a language with strings that include at least one 1

$L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence $L_2$ = Turing machines that decide $L_1$ I think the first language is decideable, as the input string is of finite ...
76 views

### Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
41 views

20 views

### Is finite subset of a set which contains all non regular languages a regular set?

Let A be a set which contains all non-regular languages. Then set B which is finite subset of A. Then will it be regular ? I know that A is not recursive enumerable set (undecidable). So I wonder ...
33 views

### I've proven my language undecidable what is left to prove it Turing equivalent?

Let us say that I have a computation model $A$. Let us also say that I have shown that $A$ can be simulated by a Turing machine. I have not been able to prove that $A$ can simulate a Turing machine. ...
111 views

### Probabilistic halting problem

I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ...
442 views

### Which languages, decided by a turing machine are decidable?

How do I decide if a language is decidable and/or semi-decidable? I have theses languages: a) { < M > | L(M) ⊆ 0*} b) { < M > | L(M) contains at least one word of even length} c) {...
76 views

### To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA? [closed]

Why can't a TM simulate a PDA? Then we can easily construct a PDA P which is made from grammar G. And contruct a TM that simulates P to prove that this problem is decidable.
76 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$-...
141 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 ...