# Questions tagged [undecidability]

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

780 questions
Filter by
Sorted by
Tagged with
615 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 ...
191 views

### Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?

I have a book that proves the halting problem with this simple statement: $$A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$$ It states that halting problem reduces to the ...
233 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

520 views

### Is the intersection of two regular languages regular?

Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given ...
147 views

161 views

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

3k views

### Examples of undecidable problems whose intersection is decidable

I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the ...
882 views

### Showing that the set of TMs which visit the starting state twice on the empty input is undecidable

I'm trying to prove that $L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$. I'm not sure whether to reduce the halting ...
203 views

### Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a ...
271 views

### Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

From this statement As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning ...
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 ...
970 views

### Is this finite graph problem decidable? What factors make a problem decidable?

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
OK, so here is a question from a past test in my Theory of Computation class: A useless state in a TM is one that is never entered on any input string. Let \mathrm{USELESS}_{\mathrm{TM}} = \{\...