233 votes
Accepted

Why, really, is the Halting Problem so important?

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem. You want a compiler that finds the fastest possible machine code for a ...
user avatar
  • 29.1k
54 votes

Why, really, is the Halting Problem so important?

In practical terms, it is important because it allows you to tell your ignorant bosses "what you're asking is mathematically impossible". The halting problem and various NP-complete problems (e.g. ...
user avatar
  • 724
48 votes

Why, really, is the Halting Problem so important?

You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1). To do that, you need to store at least two copies of the partial ...
user avatar
46 votes
Accepted

What are the simplest examples of programs that we do not know whether they terminate?

A pretty simple example could be a program testing the Collatz conjecture: $$ f(n) = \begin{cases} \text{HALT}, &\text{if $n$ is 1} \\ f(n/2), & \text{if $n$ is even} \\ f(3n+1), & \text{...
user avatar
  • 584
38 votes
Accepted

Is the halting problem decidable for pure programs on an ideal computer?

Here is a proof of undecidability by reduction from the Halting problem. Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ ...
user avatar
32 votes

Why, really, is the Halting Problem so important?

It seems to me that the Halting Problem is nothing more than a so called "paradox," a self referencing (at the very least cyclical) contradiction in the same way as the Liar's paradox. The only ...
user avatar
  • 421
32 votes

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. "...
user avatar
  • 492
31 votes
Accepted

Is it provably true/false that for a program, there exists a proof whether it halts or not?

Actually this is no different from the halting problem unsolvability. If you have any formal system T with a proof verifier program V that can reason about programs (as you desire in your question), ...
user avatar
  • 714
28 votes
Accepted

Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. ...
user avatar
  • 6,978
25 votes

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
user avatar
  • 1,090
23 votes

Are there programs that never halt and have no non-termination proof?

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt. These proofs are strings of finite length,...
user avatar
  • 29.1k
22 votes
Accepted

Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a ...
user avatar
21 votes
Accepted

Does the proof of undecidability of the Halting Problem cheat by reversing results?

Short version: The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that decides whether the input machine halts on the given ...
user avatar
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

Is halting problem computable for particular inputs/assumptions

is halting problem computable by program P for all other programs used as input but P itself? No. Consider the infinite sequence of programs $P_1, P_2, \dots$, where $P_i$ is "Move the head $i$ ...
user avatar
21 votes
Accepted

Halting Problem without self-reference: why does this argument not suffice (or does it)?

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the ...
user avatar
  • 141k
20 votes
Accepted

Is possible to prove undecidability of the halting problem in Coq?

You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement. Suppose ...
user avatar
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
20 votes
Accepted

Can a program exist that halts only if it can prove that it doesn't halt?

We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true ...
user avatar
19 votes

Why, really, is the Halting Problem so important?

jmite has answered the question really nicely. Let me add a small side-note regarding the perceived similarity with the "Liar's Paradox" which I think is caused by their usage of a self-reference ...
user avatar
  • 21.7k
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
Accepted

Why won't a Turing machine halt?

A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following: while (true) { do_nothing } , then ...
user avatar
  • 20.4k
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
19 votes
Accepted

The 'directionality' of reductions?

Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed ...
user avatar
18 votes
Accepted

Does Church-Turing thesis also apply to artificial intelligence?

The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has ...
user avatar
18 votes
Accepted

How to prove the existence of a number which cannot be written by any algorithm?

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number ...
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

Why, really, is the Halting Problem so important?

You seem to be confusing the classic "self referential" based proof that the Halting problem cannot be solved with the Halting problem (aka Halt) itself. That self-referential program -- the program ...
user avatar
  • 785
17 votes
Accepted

Why can't we solve the Halting Problem by using Artificial Intelligence?

The halting problem is not a statement about intelligence (human or artificial) it is a statement about the limits of mathematics. It is an historically important example of an undecidable problem. ...
user avatar
17 votes

Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the ...
user avatar

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