# Questions tagged [undecidability]

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

658 questions
Filter by
Sorted by
Tagged with
302 views

### Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?

I have having trouble with the following question: Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.
529 views

### Decidability of a Turing machine which always halts in at most ten steps [closed]

I have an exam coming up soon and I need help with this. Consider the problem: Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input. Is this decidable? Prove ...
13k views

### Why isn't the class of Turing-Recognizable languages closed under Complement?

I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations ...
673 views

### Program synthesis, decidability and the halting problem

I was reading an answer to a recent question, and sort of a strange, ephemeral thought came to mind. My asking this might betray either that my theory chops are seriously lacking (mostly true) or that ...
150 views

533 views

### Is it possible to decide if a given algorithm is asymptotically optimal?

Is there an algorithm for the following problem: Given a Turing machine $M_1$ that decides a language $L$, Is there a Turing machine $M_2$ deciding $L$ such that $t_2(n) = o(t_1(n))$? The ...
208 views

### Language comprising of Turing machine encodings

Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$ According to my understanding, if a Turing machine is able to decide if another Turing ...
1k views

813 views

### When are 2 decision/optimization problems equivalent?

Does anybody know a good definition of 2 decision / optimization problems being equivalent? I am asking since for example allowing polynomial time computations any 2 problems in NP could be ...
230 views

### Determining the classification of languages

$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$halts on$w$}\}$ $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$does not halt on$w$}\}$ $L = L_0 \cup L_1$ I need to determine where in ...
1k views

### Visualizing a Non Deterministic Decider

I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization ...
2k views

### Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
255 views

### Decidability of a problem concerning polynomials

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite ...
899 views

11k views

### Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to ...
338 views

10k views

### Why isn't this undecidable problem in NP?

Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that ...
2k views

### Are there undecidable properties of non-turing-complete automata?

Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability). I would like to get ...
One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following: $A \subseteq \Sigma^*$ is c.e. iff there is a ...