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 ...
- 2,010
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 ...
- 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 ...
- 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 ...
- 17.7k
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 ...
- 270k
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 ...
- 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 ...
- 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 ...
D.W.♦
- 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-...
- 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$ ...
- 80.2k
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 ...
- 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 ...
- 670
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 ...
- 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 ...
- 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 ...
- 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 ...
- 270k
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$?...
- 270k
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 ...
- 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 ...
- 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 ...
- 270k
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 ...
- 3,107
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 ...
- 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 ...
- 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}\}
$$...
- 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 ...
- 2,148
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 ...
- 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 ...
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 $...
- 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:
...
- 5,722
Only top scored, non community-wiki answers of a minimum length are eligible