# Questions tagged [undecidability]

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

712 questions
Filter by
Sorted by
Tagged with
15k views

### How can it be decidable whether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...
16k views

### How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
6k views

### What makes type inference for dependent types undecidable?

I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit ...
7k views

### Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
6k views

### Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
2k views

### Rice's theorem for non-semantic properties

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always ...
855 views

### Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
11k 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 ...
1k views

### Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
2k views

### What are the strongest known type systems for which inference is decidable?

It's well known that Hindley–Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...
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 ...
2k views

### Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
494 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 ...
12k 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 ...
322 views

### Regular expressions with backreferences over unary alphabet

Setting: regular expressions with backreferences unary language (1-symbol alphabet) Is the following problem decidable in this setting: Given a regular expression with backreferences, does it ...
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 ...
836 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 ...
3k views

### Proof of the undecidability of compiler code optimization

While reading Compilers by Alfred Aho, I came across this statement: The problem of generating the optimal target code from a source program is undecidable in general. The Wikipedia entry on ...
3k views

### Is it decidable whether a pushdown automaton recognizes a given regular language?

The problem whether two pushdown automaton recognize the same language is undecidable. The problem whether a pushdown automaton recognizes the empty language is decidable, hence it is also decidable ...
1k views

### Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
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 ...
5k views

### Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
345 views

2k views

### undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
1k views

### Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
714 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 ...
3k 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 ...
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 ...
29k views

### Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

Let $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$ Is there a Turing machine R that decides (I don't mean recognizes) the language $L_\emptyset$? It ...
1k views

### Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
843 views

### Reductions among Undecidable Problems

Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem ...
305 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 ...
564 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 ...
806 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 ...
532 views

### Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...