144
$\begingroup$

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][1] 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 (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 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. A programmer gets some programs, must determine which ones terminate, and the video goes on to explain why that's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. 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." Many algorithms are formally demonstrated to do so. The failure to make this distinction, by every single reference I found on line, 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.

$\endgroup$
  • 16
    $\begingroup$ "a deterministic machine with finite memory" is "boring" since it's nothing more than a finite automaton; these are not useful for modelling computation in general. As for the halting problem: it's a specific example for a function that is not (Turing) computable. If you are satisfied with a non-constructive proof, you don't "need" it. It still has historical relevance, though. $\endgroup$ – Raphael Nov 8 '14 at 17:00
  • 16
    $\begingroup$ That said, your question comes across as ill-informed. You might want to brush up on your fundamentals of computability theory (which will challenge your intuition which is informed by reality, not the models discussed there). See our reference questions for a start. If you require further "proof" that your intuition (as far as theory goes) is fatally flawed, go read this question. $\endgroup$ – Raphael Nov 8 '14 at 17:03
  • 12
    $\begingroup$ "You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1)" - but if you want to solve the problem for a computer with 2 GB of storage, you'll need over 2^2000000000 steps and a bigger computer. $\endgroup$ – user2357112 Nov 8 '14 at 23:02
  • 11
    $\begingroup$ A long time ago I was chatting to a friend about the halting problem and someone sitting nearby asked "what is the halting problem, is it important?" and my friend turned to him and said "if we could solve the halting problem, we could build cities on clouds". This is true. $\endgroup$ – Francis Davey Nov 9 '14 at 17:01
  • 8
    $\begingroup$ @emory The claim is vacuously true: P => Q is true for any Q, if we know that P is false (and we do know that the Halting Problem is not solvable). Francis could just as well say "If we could solve the halting problem, we could find a cure for death itself". It's the way logical implication is defined. $\endgroup$ – amalloy Nov 11 '14 at 1:48

12 Answers 12

214
$\begingroup$

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 levels, 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 to 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 Liars 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 it 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.

$\endgroup$
  • 4
    $\begingroup$ @Mehrdad For any reasonable definition of "fastest possible machine code for a given program", the question makes sense and the answer is "There can be no such compiler." $\endgroup$ – David Richerby Nov 9 '14 at 12:27
  • 13
    $\begingroup$ It also works for finding the shortest possible machine code to output, the one with the least memory acesses, etc. etc. For general programs, finding any optimal transformation is undecidable. This is basically Rice's theorem. $\endgroup$ – jmite Nov 9 '14 at 15:46
  • 4
    $\begingroup$ As a corollary to the point about still looking for Hilbert's magical algorithm, without the closely related concept of Turing equivalence, we would still be arguing over whether gotos or self-modifying code allow for more powerful computation, looking for computationally more powerful forms of hardware, and the arguments over which is the best programming language would be far more subjective even than they are now. $\endgroup$ – sdenham Nov 9 '14 at 20:47
  • 3
    $\begingroup$ It even turns up in places you wouldn't expect. Want to write a C++ compiler that rejects all invalid programs while compiling all valid ones? Solve the halting problem first -- C++ template metaprogramming is Turing-complete, so telling if your templates are valid or not in the general case requires solving it. $\endgroup$ – Mark Nov 10 '14 at 2:37
  • 7
    $\begingroup$ @Merhrdad: Your example of "simulating the entire computer program" is an excellent example of why the halting problem is so important. For some programs, simulating the program isn't as straightforward as it seems (for examples, look at the wikipedia page on halting). If the problem can be deceiving in this form, you can imagine how hard it is to explain to someone a more hidden form (such as the anti-virus problem) $\endgroup$ – Cort Ammon Nov 10 '14 at 5:59
49
$\begingroup$

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.

$\endgroup$
  • 20
  • 16
    $\begingroup$ Well, @bishop, except Flickr did the virtually impossible. $\endgroup$ – Francisco Presencia Nov 9 '14 at 0:47
  • 8
    $\begingroup$ it is possible to design a language that is not Turing-complete: Example of a useful non-Turing complete language: SQL (actually a stripped down SQL). Turing-completeness would automatically add non-termination to the language, which is something you probably don't want when running a db query. (Although, I'm afraid all modern SQL implementations offer turing-completeness anyway) $\endgroup$ – Bakuriu Nov 9 '14 at 18:12
  • 8
    $\begingroup$ @FranciscoPresencia: they used a research team, so the general point still holds. $\endgroup$ – RemcoGerlich Nov 10 '14 at 14:58
  • 4
    $\begingroup$ @MooingDuck: the Flickr thing doesn't choose between parks and birds, it (attempts to) confirm either or both. OR, not XOR. $\endgroup$ – rickster Nov 10 '14 at 18:32
44
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I would think that the question of "is there a program which would produce the same output as a given self-contained program (no input but the program itself), but in less time, including the time to load the program?" would be decidable, albeit intractable, since the maximum length of candidate programs would be bounded, as would be the time to test each one. $\endgroup$ – supercat Nov 10 '14 at 23:59
  • $\begingroup$ @supercat Yes, this property is decidable. It isn't decidable for the general case of a program that takes input. $\endgroup$ – Gilles Nov 11 '14 at 0:16
  • 1
    $\begingroup$ I was under the impression that the Halting Problem typically assumes that all of the input a program will receive in the course of its execution is bundled with the program. If one had a machine which could magically solve the Halting Problem for any program fed any particular sequence of input, could such a machine determine whether a program would halt for all bounded-length inputs? $\endgroup$ – supercat Nov 11 '14 at 0:26
  • 3
    $\begingroup$ @supercat No, the halts-for-all-input oracle would be one step further up than the halts-for-a-given-input oracle. That would make a good question for this site… in fact we have it. By the way, my default mental model is recursive functions, where “input” means “argument” and running a program means applying it to an argument; you're right that my statement is false in a context which is about Turing machines, I'll update it. $\endgroup$ – Gilles Nov 11 '14 at 0:54
27
$\begingroup$

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)$.

$\endgroup$
  • 2
    $\begingroup$ It's worth noting that in the common form the Liar's Paradox makes explicit reference to itself, but the same problem can arise even if it doesn't. Is the answer to the statement formed by taking the text, "Is the answer to the statement formed by taking the text, and inserting after the first comma a copy enclosed in quotes, no?" and inserting after the first comma a copy enclosed in single quotes, no? Such a statement is not explicitly self-referential but refers to the truthfulness of a statement which is character-for-character identical. $\endgroup$ – supercat Nov 11 '14 at 16:57
  • 2
    $\begingroup$ @supercat: huh, I don't think I've seen a quine in English before ... $\endgroup$ – SamB Nov 11 '14 at 23:41
  • $\begingroup$ @SamB: I've seen a few, but decided to try my hand at an original formulation which, while more verbose than some, reads (perhaps) more naturally. $\endgroup$ – supercat Nov 12 '14 at 14:40
23
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 for explaining the relationship between real computers, finite state machines and Turing machines which is a significant part of the setup to the question. $\endgroup$ – David Richerby Nov 9 '14 at 12:20
  • $\begingroup$ You've piqued my interest. What's the difference between an apparent contradiction and a real contradiction? $\endgroup$ – Brent Nov 10 '14 at 15:34
  • $\begingroup$ Another way of putting this: generally speaking, programming doesn't assume limited resources.Most of the algorithms we design or programs we write are not written to use a limited, or even fixed, amount of computing resources, unless we specifically design them that way (e.g. this is often required when programming for embedded systems). $\endgroup$ – reinierpost Nov 11 '14 at 5:40
  • 3
    $\begingroup$ @Brent. Many paradoxes are not contradictory at all, but only on first sight. When we look closer, there turns out to be an error in the reasoning, or some word of which the meaning slightly changed by using it in a different context, or something similar. Sometimes, however, a paradox brings to light a real contradiction. $\endgroup$ – Hoopje Nov 11 '14 at 12:22
  • $\begingroup$ I've been studying this problem on and off since my OP. Does Gödel's incompleteness theorem imply that it's always possible to come up with some paradox regardless of the system of logic in use? $\endgroup$ – Brent Oct 30 '15 at 14:20
17
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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


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

$\endgroup$
  • $\begingroup$ You might want to explain what a "property" is, since the naive interpretation one might make will likely be incorrect. $\endgroup$ – Rick Decker Nov 10 '14 at 14:12
  • $\begingroup$ @rick I think the footnote covers it now? $\endgroup$ – Yakk Nov 10 '14 at 14:36
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I don't follow. The halting function is a perfectly well-defined and valid predicate -- for any given Turing machine and any given input, the machine halts or loops. (You lack a proper reference; which papar are you summarising?) $\endgroup$ – Raphael Nov 14 '14 at 11:15
  • $\begingroup$ @Raphael That the function is well-defined is generally accepted as a fact. Hehner's point of view is different and is explained in his papers. I'll edit my answer to provide the names of the papers. $\endgroup$ – Theodore Norvell Nov 14 '14 at 12:03
  • $\begingroup$ Let's just say that whatever Hehner's argument is [I haven't read the papers] they turned out controversial at least in their first reading/approximation: 'cs.toronto.edu/~hehner/Shallitaffair.pdf and recursed.blogspot.com/2013/10/eric-hehner-replies.html $\endgroup$ – Fizz Feb 21 '15 at 3:35
  • $\begingroup$ And it's not clear given the nature and number of citations that Hehner's papers (on this) have that any additional readings (of his works on this) are worth the hassle. $\endgroup$ – Fizz Feb 21 '15 at 3:47
  • $\begingroup$ His proofs seem very solid and is pointing that it is just a rehashing of silly things you can do in philosophy like trying to analyse the following self referential statement for its truthfulness: "This sentence is false." which if true means it is false which means it was actually true, no that makes it false again... so this looks like a not so important philosophical naval gazing question. en.wikipedia.org/wiki/Liar_paradox the halting paradox may be a case of scientists not talking to philosophers. $\endgroup$ – James Wakefield Oct 13 '16 at 5:12
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But if I would execute doesHalt(programCode, input);, the program cannot know what the doesHalt function returns. It is impossible for the program to un-halt after the doesHalt function has evaluated it. $\endgroup$ – Tvde1 Dec 29 '18 at 11:53
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you are mixing "Turing-undecidable" with a very different notion; in fact, you may have stumbled into the "same old" fallacy by accident. See also here and here. $\endgroup$ – Raphael 6 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.