21 votes
Accepted

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

In your edit, you write: What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less ...
user avatar
21 votes
Accepted

Is the infinite language unrecognizable in a Turing machine?

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable. A language is ...
user avatar
  • 6,940
20 votes
Accepted

Halting problem theory vs. practice

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of ...
user avatar
  • 3,728
19 votes

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

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context. Remember that Turing ...
user avatar
19 votes

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO. In other words, $\emptyset$ is decidable. You might be confused ...
user avatar
17 votes

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

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of ...
user avatar
  • 28.2k
17 votes
Accepted

Is it decidable whether a given context free grammar generates an infinite number of strings?

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive ...
user avatar
  • 16.2k
15 votes
Accepted

undecidable problem and its negation is undecidable

Consider the following language: $$L_2 = \{(M_1,x_1,M_2,x_2) : \text{$M_1$ halts on input $x_1$ and $M_2$ doesn't halt on input $x_2$}\}.$$ $L_2$ is undecidable and not semi-decidable, and same is ...
user avatar
  • 141k
14 votes
Accepted

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

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet. Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-...
user avatar
  • 27.6k
14 votes

Is it possible that the halting problem is solvable for all input except the machine's code?

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ ...
user avatar
14 votes
Accepted

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

The language $\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$ is not an index set, that is it is not of the form $\qquad L_P = \{ \langle M \rangle \mid M \text{ is ...
user avatar
  • 70.9k
13 votes

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

No. Quantum computers cannot solve undecidable problems. A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could ...
user avatar
13 votes

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

Self application is not a necessary ingredient of the proof In a nutshell If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine ...
user avatar
  • 19.1k
12 votes
Accepted

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

There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which ...
user avatar
  • 10.8k
11 votes
Accepted

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

Yes, there are such proofs. They are based on the Low Basis Theorem. See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or ...
user avatar
  • 21.7k
11 votes
Accepted

Dovetailing in Turing Machines?

Dovetailing is when you simulate two or more Turing machines in parallel on a single Turing machine. Your operating system uses this technique all the time. Why is dovetailing useful? Here is one ...
user avatar
11 votes
Accepted

Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

It's easier to think of $A$ as a list of natural numbers. If $A$ is decidable, then we can list all numbers in $A$ in increasing order by just testing all of them in order – Is $0 \in A$? Is $1 \in A$?...
user avatar
10 votes
Accepted

Is Deciding Decidability Decidable?

Major edit of my original: A naive reading of your question seems to be, let $P$ be the problem $P=$ Given a language, $L$, is it decidable? Then you ask Is $P$ decidable? As D.W. and David ...
user avatar
  • 14.6k
10 votes

Is it decidable whether a given context free grammar generates an infinite number of strings?

Without loss of generality¹, assume that the input grammar $G$ does not have $\varepsilon$-rules² and is in reduced form. That is, every non-terminal appears in at least one derivation (starting ...
user avatar
  • 70.9k
10 votes

Is it decidable if a TM takes at least 2016 steps on all inputs?

A Turing machine only sees (at most) the first 2015 symbols of the input in its first 2015 steps. Hence whether it stops within 2015 steps depends only on the first 2015 symbols of the input. This ...
user avatar
10 votes

Is L={<M>|M is a TM and L(M) is uncountable} decidable?

This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it. (I ...
user avatar
9 votes
Accepted

Is Post's Correspondence Problem decidable with fixed word size?

For all $m \geq 3$, the problem is undecidable. Proof by reduction from the word problem of unrestricted grammars: Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have ...
user avatar
  • 70.9k
9 votes
Accepted

Undecidability in the context of modern programming languages

Short answer: No. Undecidability is a property of problems, not of programs. What is undecidable is however to check if some given program ever halts on any input. This problem has the program as ...
user avatar
  • 2,682
9 votes

Is the language of Turing Machines that halt on every input recognizable?

Preliminary Let $H$ be the usual halting language: $$ H=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\} $$ Its complement is $$ \overline{H}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\} $$...
user avatar
  • 14.6k
9 votes

Unprovable Post correspondence problem instance

The argument you outline doesn't actually work. In fact, for any specific PCP instance, there is an algorithm which produces the right answer; it is either "output 'yes'" or "output 'no'". It is only ...
user avatar
9 votes

Is Deciding Decidability Decidable?

As we have seen in the different answers, part of the answer is in formulating the right problem. In 1985 Joost Engelfriet wrote "The non-computability of computability" (Bulletin of the EATCS number ...
user avatar
  • 27.6k
9 votes
Accepted

Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

The problem Do two halting Turing machines accept the same language (or compute the same "function")? is undecidable. Let $M$ be an arbitrary Turing machine. Let $M'$ be a Turing machine that on ...
user avatar
9 votes
Accepted

Decidability of checking an antiderivative?

The short answer to your question is "no". Richardson's theorem and its later extensions basically state that as soon as you include the elementary trigonometric functions, the problem of deciding if $...
user avatar
  • 18.9k
9 votes
Accepted

Undecidability of telling if a program returns true or false

Assume you have a function like the one you described: ...
user avatar
  • 5,722

Only top scored, non community-wiki answers of a minimum length are eligible