Why, really, is the Halting Problem so important?

Question

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 with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).

It seems to me that the Halting Problem proof is nothing more than a so-called "paradox," a self-referencing contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions.

So, excluding paradoxical programs, the Halting Function is decidable. So why do we hold it as evidence of the contrary?

4 years later: When I wrote this, I had just watched this video (update: the video has been taken down). A programmer gets some programs, must determine which ones terminate, and the video goes on to explain that it's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. I knew many real-life algorithms had already been formally proven to terminate. The concept of generality was lost somehow. It's the difference between saying "some programs cannot be proven to terminate," and, "no program can be proven to terminate." The failure to make this distinction, by every single reference I found online, was how I came to the title for this question. For this reason, I really appreciate the answer that redefines the halting function as ternary instead of boolean.

Answer 1

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 given program? Actually the halting problem.

You have JavaScript, with some variables at a high security level and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.

You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.

You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.

As for the Wikipedia example, yes, you could model a modern computer as a finite-state machine. But there's two problems with this.

1. Every computer would be a different automaton, depending on the exact number of bits of RAM. So this isn't useful for examining a particular piece of code, since the automaton is dependent on the machine on which it can run.

2. You'd need $2^n$ states if you have n bits of RAM. So for your modern 8GB computer, that's $2^{32000000000}$. This is a number so big that wolfram alpha doesn't even know how to interpret it. When I do $2^{10^9}$ it says that it has $300000000$ decimal digits. This is clearly much too large to store in a normal computer.

The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.

If we didn't have the halting problem, we would still be searching for Hilbert's magical algorithm which inputs theorems and outputs whether they're true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.

UPDATE: Just to address a couple of issues raised in the comments.

@Tyler Fleming Cloutier: The "nonsensical" problem arises in the proof that the halting problem is undecidable, but what's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.

The difficulty of a problem can be related to the number of quantifiers it has. Trying to show that there exists ($\exists$) an object with an arbitrary property, you have to search until you find one. If none exists, there's no way (in general) to know this. Proving that all objects ($\forall$) have a property is hard, but you can search for an object without the property to disprove it. The more alternations there are between forall and exists, the harder a problem is.

For more on this, see the Arithmetic Hierarchy. Anything above $\Sigma^0_0=\Pi^0_0$ is undecidable, though level 1 is semi-decidable.

It's also possible to show that there are undecidable problems without using a nonsensical paradox like the Halting problem or Liar’s paradox. A Turing Machine can be encoded using a string of bits, i.e. an integer. But a problem can be encoded as a language, i.e. a subset of the integers. It's known that there is no bijection between the set of integers and the set of all subsets of the integers. So there must be some problems (languages) which don't have an associated Turing machine (algorithm).

@Brent: yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.

It also has to be said that there are going to be many times where the algorithm says "this code will halt" because the code will fail and run out of memory, and that adding a single extra bit of memory would cause the code to succeed and give a different result.

The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.

Answer 2

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. the traveling salesman problem) come up a lot in the form of "Why can't you just make a program that does X?", and you need to be able to give an explanation of why it's impossible or infeasible within the remaining lifetime of the universe.

Do note that it is possible to design a language that is not Turing-complete, so can be analyzed, by forbidding unbounded recursion and iteration.

Answer 3

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 state of the program in memory, plus the overhead of the checking program. So on a given computer, you cannot test all programs that can execute on that computer, only the programs that execute on a smaller computer with less than half as much memory.

The halting problem for a given finite-size computer cannot be solved on that finite-size computer. It can only be solved on a bigger computer. (This is true for any method, not just the one you propose. I'm not going to give a formal proof, but here's the gist. If a computer C can run N different programs of which at least one P doesn't terminate, then a computer V that can test whether these N program halts must be able to run N different verifier programs too. If C and V are the same computer, then P isn't one of the N different programs that V runs, so the computer must run at least N+1 different programs, which contradicts the assumption that C runs N different programs.)

In addition, you can't just use the algorithm to detect a loop in a linked list. You need to know when to stop. You can stop once you've executed as many steps as there are states in the computer. If a program uses up to $M$ bits of memory, then it can have $2^M$ different states. This very quickly becomes impossible. For example, a typical computer executes on the order of a billion instructions per second; one billion seconds is a little over 30 years. So if you run a computer for 8 years, you can test whether one program with about 250 million billion potential states halts. But that's only $2^{56}$ states, i.e. you can only test a program that works in 7 bytes of memory.

The numbers there illustrate that thinking of a computer as a finite-state machine is rarely practical. The number of states may be finite, but it's mind-bogglingly, impractically huge. The only way to reason about non-toy programs is in the abstract, not by enumerating states but through logical reasoning.

So excluding paradoxical programs, the Halting Problem is decidable

The paradox does not come from the problem, but from the attempt at a solution. For any given program, there is an algorithm that says “yes” if the program terminates, and “no” if the program doesn't terminate. It's trivial: either print "yes" or print "no" will do. The problem is to determine which one to call. The impossibility of solving the halting problem means that there is no algorithm to make this determination. The reason the proof uses a diagonalization argument is that it needs to show that no solution works; to do that, it starts from an arbitrary purported solution, and shows that it must miss some programs by constructing a missed program. The diagonalization (what you inappropriately call a “paradox”) is in the construction, not in the resulting program. The resulting programs is not self-referential.

There is a more general result called Rice's theorem which states that any non-trivial property of programs is undecidable — any property that depends only on the behavior of the program and not in the specific way it's written (for example, “does the source code consist of less than 42 characters?” is clearly decidable, whereas “is there a program whose source code consists of less than 42 characters and that returns the same result for all inputs?” is not, nor is “does this program ever output anything?”). Halting is just one example. It's an important one because it often comes up in practice (usually, we want to know whether a program will return a result in reasonable time given the finite resources of the computer it's running on, but since this is rarely practically answerable, we're willing to settle for the simpler question as to whether the program will eventually terminate given enough time and memory).

Answer 4

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 conclusion it makes is that the Halting Function is susceptible to such malformed questions

No, that's not what the halting problem is about. Paradoxes like the liar's paradox aren't true or false, they simply don't make sense. A deterministic algorithm on the other hand will either halt for a given input or it will run forever. The function halts(program, input) has a perfectly well-defined, deterministic value for every program, for every input. We just can't decide it for any program. Or, more precisely: We can't write a program that can decide it for every program/input pair.

A similar (maybe less abstract) example is the "busy beaver" function, intuitively defined as $\Sigma(n):=$The longest sequence of 1's a Turing machine with $n$ states, starting with an empty tape, can write before it terminates. For any $n$, there's only a finite number of Turing machines, and each of them either terminates at some point (then you can count the number of ones), or it runs forever (then the busy beaver doesn't carea about it - it only looks at programs that terminate). So, the busy beaver function has a deterministic value for every $n$. (We even know it for a few small $n$, because we can look at each program and find proofs why they will never halt.) But there can't be a program that calculates $\Sigma(n)$.

Answer 5

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 with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).

First, yes, theoretically it makes sense to view a real computer, which has finite memory, as a finite state machine. But in practice the number of states of a real computer is so large, that real computers are much better modelled by Turing machines or other infinite state models of computation.

And second, even theoretically it makes sense to view a modern computer as an infinite state machine. A Turing machine does not have an infinite tape, it has a tape which can always be extended when the machine runs out of memory. And isn't that exactly what we can do with real computers? (And if the address space of the CPU runs out, we can use the cloud, etc.)

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 conclusion it makes is that the Halting Function is susceptible to such malformed questions. So excluding paradoxical programs, the Halting Problem is decidable. So why do we hold it as evidence of the contrary?

There is a difference between the halting problem and the proof of its undecidability. The halting problem is just a specification for a program $H$: as input the program gets the source code of a program $P$ and an input $x$, and the program $H$ must return true if $P$ halts on input $x$ and false otherwise. This is a very clear specification; there is nothing paradoxical about it: every pair of source code and input has a single well-defined correct answer.

Turing's proof of the undecidability of the halting problem uses a trick which is similar to the Liar paradox, yes. A paradox is often defined as a apparent contradiction, and some people infer from that that a paradox is therefore not a real contradiction. However, Russel's paradox (the formal set-theoretic counterpart to the liar's paradox) showed a real contradiction in mathematics, and the proof of the undecidability of the halting problem uses a real contradiction for its proof by contradiction.

Answer 6

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 mechanism.

Self-reference is not paradoxical!

Self-reference is a really useful tool in computation (that an algorithm can refer to its code, reflection) and human language (that we can refer to ourselves, self-consciousness).

The problem that causes the Liar's Paradox is not self-reference, it is trying to use the truth predicate for a (formal) language inside the language. It will cause problems even without self-reference, we don't need the ability to use self-reference to get a paradox: self-reference can be eliminated!. It would just make the sentence less nice and concise but it is not difficult to do. It is essentially how Kleene's Fixed Point theorem is proven. What the Liar's Paradox implies is that truth of statements in a (formal) language is transcendental to that language, not that self-reference is problematic.

---

It seems to me that your discomfort is not because of the undecidability of the halting problem (for Turing machines) but with acceptance of Turing machines as the theoretical model for computers. Typically (though not always) Turing machines (and equivalent models of computation like Random Access Machines) are much useful for discussion of computation on actual computers than finite automata and there are good reasons for that (keep in mind that a Turing machine does not have an infinite amount of memory, it has an unbounded amount of memory and these are different things: unbounded means that we can provide the machine with more memory when it needs, not that it uses an infinite amount of memory).

Sure, if you want to think of computers as finite automata, and that makes sense for your purpose, then the halting problem for finite automata is decidable (and by decidable we mean decidable by a Turing machine, not by a finite automata). That is however not what people normally mean when they use the halting problem, they mean the halting problem for Turing machines.

Also note that automata theory is actually used a lot in program analysis and software verification. If you know that $s$ is an upperbound on the amount memory your algorithm is going to use, it cannot run for more than $2^s$ steps and halt. But 1. it needs you to know an upperbound on the amount of memory the algorithm is going to use, 2. even then the decision whether that algorithm halts or not takes an exponential amount of time which is usually not a very useful algorithm.

Answer 7

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 that halts if and only if it doesn't halt -- is constructed in order to make it easy to prove you cannot solve Halt. The fact that we prove X is impossible via technique Y does not imply Y is the only reason why we cannot solve X.

To put it another way, not only can we not solve Halt, we cannot detect that a program the kind of program that we cannot determine if it Halts, other than a crude measure like "if it takes more than 1 minute to run, pretend it does not halt".

If you start from the Halting problem, and reduce other problems to it, you eventually reach the point that you have reduced almost every question about programs about it. We end up with Rice's Theorem:

Let S be some non-trivial property of¹ what a Turing Machine accepts. That means there is at least one Turing Machine that accepts input with property S, and one that does not.

Then it is undecidable if a given Turing Machine T accepts input with property S.

You want to know if a Turing Machine accepts even integers? Undecidable.

You want to know if a Turing Machine accepts accepts arithmetic sequences? Undecidable.

You can reason about Turing Machine's guts in general. You can reason about a particular Turing Machine, and prove if it will halt/accept some sequence/etc. But you cannot know if your technique will work on the next Turing Machine you feed it.

---

¹ By property of it does not include the mechanism of how it is accepted -- just of what is accepted. "It accepts in 100 or less steps" is a property how it accepts, not of what is accepted.

Answer 8

the halting problem introduced a new mathematical concept of "undecidability" that did not previously exist in mathematics. it was a ("seemingly paradoxical") proof that some problems have no "proofs". its connected to the Godelian concept of unprovability. Godels theorem preceded the halting problem formulation by Turing by a few years. Godels result was considered rather abstract at the time and was only known to researchers and specialists. Turings formulation showed that the principle of undecidability was related to highly practical/ pragmatic/ applied questions in computer science such as determining whether arbitrary programs halt and it is regarded as a far less theoretical concept, it shows up in modern challenges such as "automated theorem proving" (a challenge whether computers can discover theorems) and proving program termination.

another interesting angle is that there are some very old problems in (Diophantine) number theory originating with the Greeks that are unproven for millenia. there is a related result that general questions on Diophantine equations are undecidable called Hilberts 10th problem/ theorem. Hilbert lived at the turn of the 20th century and proposed as a research program that mathematics could find systematic approaches to math problems. this challenge/ plan was seriously struck by the discovery of undecidability from a few decades later. undecidibility continues to be a very advanced area of research and the boundary between undecidable and decidable problems will probably always be under further study and analysis.

Answer 9

You are right that the halting problem as commonly introduced and stated is a mere gotcha. It doesn't prove that there cannot be a three-valued (‘halts’, ‘loops’, ‘don't know’) halt-function that in practice always returns ‘halts’ or ‘loops’ and only returns ‘don't know’ for specially constructed corner-cases for example.

Two reasons the halting problem is significant:

1) This is one of the first provably undecidable problems. Even if hypothetically there were only one ‘don't know’, it would still be of huge mathematical interest.

2) Some problems reduce to the halting problem where a malicious attacker can supply the case to be analysed. This forces us to accept that there may be valid cases that we still have to reject.

As an afterthought to the second point, software analysis is a hard problem, although a lot of progress has been made both in analysis and in language design so as to make analysis easier. If you can show that a certain task is similar to software analysis, yes, it's Hard with a capital H. ‘It's impossible because it would amount to solving the halting problem’, although technically wrong or irrelevant in many cases, is often used a shorthand for this observation.

Answer 10

There is a contrarian argument put forth by Eric Hehner in a series of papers that argue that the unsolvability of the Halting Problem is commonly misunderstood. The papers, " Epimenides, Gödel, Turing: an Eternal Golden Tangle", "Problems with the Halting Problem", "Reconstructing the Halting Problem", and "Halting Problem", can be found here. So that this answer is not "link only" I will try to summarize one of his conclusions, but not the argument.

The conclusion is that: the reason that the halting problem is unsolvable is not because a program purported to solve it can be used to create a contradiction, but rather because the problem itself is unimplementable, in the same sense that a specification of a function that must return both 1 and 2 at the same time is unimplementable. We don't find it remarkable that there is no program to satisfy a specification $f(0)=1 \;\land\; f(0)=2$, so we shouldn't find it so remarkable that there is no program to solve the halting problem. The standard view is that there is a well-defined predicate $h$ such that $h(M)$ is true if Turing machine $M$ halts on a blank tape and false otherwise, but that there is no program $H$ that implements $h$. Hehner's view is that the predicate $h$ is not well defined to start with.

Answer 11

I would like to offer a different explanation of the importance of the halting problem that involves people rather than machines.

It's the last lecture of the MIT 1986 Structure and Interpretation course; the professor asks "Are there any questions?" and prepares to end the lecture, when one of the students asks: "Is this the last question?"

Think about it for a moment. How can the teacher answer this? If the student decides to contradict the teacher, there is no valid answer the teacher can give - this is just like the halting problem.

We're used used to think about the halting problem abstractly, using functions and machines, but it's much deeper than that. Fundamentally, it means that there are perfectly valid questions that cannot be answered.

PS: If you don't know what course I'm talking about, go watch it, it's awesome.

Answer 12

I can easily write a program which given an input n, either outputs the smallest prime p > n such that p+2 is also a prime, or runs forever if no such p exists. If you can solve the problem to predict whether my program halts for every input, you just solved the Twin Prime Conjecture.

It is quite possible that this conjecture might be proven undecidable, in which case we’d have a straightforward program where the halting program fails.

Answer 13

I’m not going to address the math or science, except to say it proves we can’t do a whole bunch of things and that there are even more where we can’t say they are solvable until we have solved them.

Instead I’m going to address what seems to be a common emotional reaction to the Halting Problem: that it is a cheap trick like a little boy running around chanting “fooled ya, fooled ya. I’m rubber, you’re glue whatever bounce off of me sticks to you”.

If the Halting Problem was a song it would be a dirge. It ends the idea that all problems can be solved with computers. This new toy we had created was not as boundless as it had at first seemed. Some problems are and will remain, forever unsolvable. What’s even worse, is that in many cases there’s no way to tell the difference between “unsolvable” and “solution not know”, only between “solved” and “unsolvable”.