# Questions tagged [undecidability]

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

780 questions
Filter by
Sorted by
Tagged with
910 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 ...
274 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 ...
3k 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 ...
339 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 ...
1k views

14k 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 ...
385 views

12k 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 ...
928 views

### Can we show a language is not computably enumerable by showing there is no verifier for it?

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 ...
4k views

### Operations under which the class of undecidable languages isn't closed

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable ...
6k views

1k views

### Is it possible to solve the halting problem if you have a constrained or a predictable input?

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For ...
1k views

### Is there a "natural" undecidable language?

Is there any "natural" language which is undecidable? by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the ...
519 views

### Ratio of decidable problems

Consider decision problems stated in some “reasonable” formal language. Let's say formulae in higher-order Peano arithmetic with one free variable as a frame of reference, but I'm equally interested ...