General Halting Problem Problem

[[What follows below is simply misunderstanding about the Halting Problem and the proof that it is undecidable. Instead of P and Q, below, let me use Halt for the alleged program (of one argument) that solves the Halting Problem, and Spoiler the program (of zero arguments) that shows that Halt cannot work. It is a plain and simple result that Spoiler will cause Halt to fail. That is unavoidable. If you want, you can take the text of Spoiler, and incorporate it into another program Halt1, which tests to see if its input is the program Spoiler. But that program Halt1 will have its own Spoiler1. There is, quite simply, no way to avoid this. It simply does not matter what sort of examination Halt makes of its input tape, or whatever. Spoiler takes Halt as given, and is constructed to make Halt fail. That's it. End of story.

Nor are the attempted objections to the misunderstanding relevant. Even if Spoiler includes the text of Halt directly in some sense, Halt will not be able to exploit that fact. Spoiler is constructed by definition to make Halt fail, the proof that it does so is simple. There is no need to invoke an "obfuscated" version of Halt inside a virtual machine to thwart it. In fact, the problem of whether or not an obfuscated version of a program is equivalent to the original version is also undecidable (it is the problem of program equivalence), but this fact is proven by reducing the halting problem to the problem of program equivalence, not vice versa.

But ... there is apparently an even more basic misunderstanding which has to be addressed, because of the potential mechanics of Turing Machines and how they might be put together

It was to clear up this misunderstanding that the argument about an "interpreter" was invoked below. Let's summarize it up here. It relies specifically on Turing Machine formulations of the problem. Halt is defined so that, on a tape that contains nothing but a description of a 0-argument Turing Machine, it runs and leaves a tape which contains only a 0 or a 1, depending on whether or not the given Turing Machine halts on an empty tape. (This is all without loss of generality, I think everyone can agree.). The alleged refutation relies on the fact that when Halt is run, it need not assume that the tape is empty except for its own input. The tape may contain some other markings that a containing program, such as Spoiler, has placed on the tape. It is alleged that by examining these markings, Halt can alter its output to get around the problem Spoiler presents it with. But this is quite simply false. This is where the "interpreter" comes into play (not to obfuscate, as I thought was being suggested, but) by preventing the version of Halt contained within it from accessing anything outside what it would be able to access had it been started under normal conditions. In fact, it is not Halt that is contained within Spoiler, but a lobotomized version of it that forces it to work only on the Halting Problem and not anything else weird involving going outside its own input. It may be objected that this is not fair, restricting Halt in this way, but of course it is totally fair, because there is no obligation to include Halt inside Spoiler. All that is required for the simple proof to go through is a program that is input-output equivalent to Halt when it is started on as tape containing nothing but the program whose halting status it is supposed to ascertain. An "interpreter" of some form may be required to do this (such as one that simulates that otherwise empty tape, even while the program doing the simulation writes other stuff on the "real" tape). But the key is that the modified Halt, contained as a subroutine in Spoiler, is input-output equivalent to the original Halt on the actual problem that was given to the original Halt. It is irrelevant that it is not input-output equivalent on some other strange problem.]]

Well said, that's right on target. On the last point, though, it's worth noting that there are many, many different ways of proving that program equivalence is undecidable, and equivalently, that there are an infinite number of algorithms/functions/machines that compute any given thing, not just the proofs that depend on the halting problem as a lemma. One of the more startling ones is the Speedup Theorem: there is no such thing as the fastest program; there's an infinite series of programs, each a bit faster than the previous, yet all computing the same thing. But yes, in any case, that result demonstrates that you cannot hope to simply recognize which machine is input, since there are an infinite number of variations on the same theme. -- Doug
So let me see if I have this version of your collective arguments straight now: to prove that there is no P, we invoke P(Q(I(P(Q(P'], where I is a provably uncrackable (by P) UTM or LC equivalent interpreter, and P' is any source that expresses exactly the same function as P, but without having the same representation as P, this being to prevent the invocation of P that's invoked inside the outer Q from determining that P' is computationally equivalent to P. And I'm to take it on faith that, both without assuming the antecedent of non-recursive halting (which, being the fundament of so many such proofs, I rather suspect is after all assumed, but will let it go), you can demonstrate the undecidability of program equivalence, and the uncrackability of I. I do not mean to cause you any more upset than is strictly necessary here, Doug, I just want to make sure I understand what you're claiming before generating more ThreadMess. -- Pete

[[Uh, no. There is no need to be concerned with the undecidability of program equivalence here. There is no need for "uncrackable" anything, whatever that means, and certainly the version of Halt used by Spoiler (Halt') is more than "any source that expresses the same function" as Halt (how would one find such a thing if not as a provably equivalent minor modification of Halt itself?) It is in fact essentially Halt, but Halt restricted to run on a tape that it was required to be designed for. Note that Halt must be able to run on a tape that starts with nothing on it but a representation of the program it is required to test. It may contain some extra code to look elsewhere on that tape in order to see if it is "being tricked", however, it must be able to solve the Halting Problem without applying that code, in the circumstance that it is started normally on a tape containing only its own input. It is thus a simple matter for Spoiler to take the tuples defining Halt, and alter them so in effect they are running on a virtual tape/head combination, instead of the real tape/head (which is simulating them), and, most importantly, deliver the same answer as would be delivered by Halt running on the real tape/head combination, which, by the claim of its author, has input/output behaviour defining the Halting Problem, and which is the minimum anyone claiming to solve the Halting Problem must be able to provide. Given this using of the simulated Halt, which has input/output behavior equivalent to the original Halt, it is the usual simple proof to show that Halt applied to Spoiler cannot deliver a consistent result.

You know, computability theory is a highly developed and very interesting discipline. Do you really think you have found some problem at the very basis of it that renders all of the deep and complex results (such as those describing the highly complex structure of the recursively enumerable degrees) somehow flawed? Perhaps you should have a little less hubris. I see this has all been explained before, below, although perhaps the explanation that stays at a more concrete level (keeping always in mind that we are dealing with concrete Turing Machines, not lisp machines, abstract environments and interpreters not directly reduced to Turing Machines, etc) may be more helpful. But maybe nothing is helpful for a troll?]]

Brand new semi-humorous argument: my machine P is both a GeneralHaltingProblem solver and also good at inferring the intent of its input. When invoked as Q's inner loop, P will examine its input (source of Q) and immediately realize that it (P) is being used in a misguided attempt to prove that it (P) cannot actually exist. It (P as Q's inner loop) will consequently print "0" - causing Q to halt - while simultaneously adding states to its (Q's) FSM which, when inspected by the outer invocation (P), explain the subterfuge, permitting it - the outer invocation of P - to assert the correct halting value. Which is, correctly, "1".

Please email the Nobel to Pete@that-place-I've-gone-to.com. Thanks!

But seriously, where's the logic error above?

You're brilliant, Pete, but you just overstepped the limitation of Turing Machines. Programs for TM are deterministic, and therefore two runs of the same program for the same input cannot give different results.

If we allow for non-determinism, then, yes, you can make a program P that somehow (magically) distinguishes when it is run from the supervision of Q and does whatever trick it needs. But then, you haven't disproved the HaltingTheorem because such a program cannot be constructed in TMs. So, you don't get the Nobel.

Ah, but P doesn't act non-deterministically; it merely inspects all the contents of the tape - including its own outer invocation. This is to say, the way it makes its distinction about whether to print a subterfugal "0" is to see all the universal-turing-machine gear, the source of its own outer invocation, and so on. It's all there on the tape, and in finite form, so it's easy for it to do deterministically.
- Well, you assume that it is easy for your program P to determine the context in which it is invoked, but that ain't the case. To make it more clear, let's put it first in Scheme, then in pure lambda calculus:

 ;assume we have a program p
 ;without side-effects, in Scheme
 (define p (lambda (x) <body-of-p>))

 ; and p solves the halting question for a program x returning
 ; true if (x) halts and false otherwise.

 ; then we define the program q 
 (define (q) ( if (p q)
                   (loop-forever)
                   #t))
 ; and if p doesn't have side-effects (it is purely functional)
 ; then (p q) should yield the same result in all context,
 ; and it is easy to see that
 ; (p q) = true implies q loops forever

 ; Now the inventive Peter, will protest that q has access to an environment 
 ;(which makes the recursive invocation (p q) possible, so then if p has access to the 
 ; environment than p can distinguish the places of invocation
 ; therefore the only technical trick to be done is to de-recursify q,
 ; remove all access to the environment while keeping it a program equivalent with the above,
 ; To do that we use a fixed-point combinator like the U
 ; http://okmij.org/ftp/Computation/fixed-point-combinators.html
 (define U (lambda (f) (f f)))

 ; we can then define q as
 (define q (U
  (lambda (f) (if (p f) 
                    ((lambda (x) (x x))(lambda (x) (x x)));loop forever
                    #t))))
 ; now we eliminated the recursion while keeping q the same
 ; let's inline the lambda expression for U and p
 ; let's inline the lambda expression for U and p
 (define q ((lambda (f) (f f))
   (lambda (f) (
        if (
              (lambda (x) <body-of-p>) ;p actually, applied to
                   (f f))                        ; applied to (f f), which is actually a stand-in for q,
              ; then
                    ((lambda (x) (x x))(lambda (x) (x x)));loop forever
              ; else
                    #t))))
 ;therefore if <body-of-p> exists with the above property, 
 ;there exists the lambda expression denoted by q 
 ;and evaluating 
 ((lambda (x) <body-of-p>) ; p applied to
                                 ; q unrolled
    ((lambda (f) (f f))
     (lambda (f) (
        if ((lambda (x) <body-of-p>) (f f)) 
                    ((lambda (x) (x x))(lambda (x) (x x)))
                    #t))))
 ;we reach the conclusion that body-of-p cannot 
 ;exist with the specified properties

Now, because in pure lambda calculus a program is simply evaluated (or technically reduced according to the rules) and doesn't have any kind of access to any environment, inspecting the stack, etc, it is a basic property that if (f a) "terminates" it always yields the "same" result (modulo renaming, etc). Then constructing the above lambda expression, if it evaluates to "true" ( known as (lambda (x y) x) in lambda calculus), it follows that it doesn't evaluate at all. So that's it.
Because of the restriction of lambda calculus it is thus less appealing to claim that <body-of-p> can detect the context in which it is evaluated (there's simply no such mechanism in the lambda calculus formalism), so if p cannot exist in lambda calculus, p cannot exist inside a TM (unless you want to disprove the equivalence between LC and TM).
I don't have to - you just did! So now we need two Nobels. What a good day.
Actually, I've been told by reliable sources that TM and LC are really computationally equivalent :) While you certainly have not produced code for your P. Let's call your P, P_TM. I produced a mapping from an P_LC to a Q_LC that proves that P_LC cannot exist. This strongly suggest that your P_TM does not exist, lest the widely held conviction about the equivalence between TM and LC is wrong. So somebody needs to dig a reference to Turing's proof about the equivalence between LC and TM and verify that, but I rather suspect it's just a matter of technique, cause it's obvious to me how to implement a TM in a purely functional Scheme (and consequently in LC). The less obvious is implementing a LC interpreter in TM, but in the end we'll implement somehow some assembly language primitive in TM, and use it to emulate x86 assembly, and then existing interpreters for Scheme are good enough to show that LC can be encoded inside the TM universe.
I had heard that somewhere, yes :) But the gap in the TM frame I drove my truck through is that nothing prevents P or Q from examining and modifying any and all of the tape. I had thought of self-refuting by showing that the inner P couldn't count on the Q code dwelling within a finite distance on the tape ... but of course then that would go for Q not being to get at P too. You adroitly spotted the whole in my hole and have ably plugged it for Post. Basically, P can't be permitted to figure out that it's testing itself. As far as I can see, nothing in the Turing UTM construction prevents this, so that's that for him. Worth noting that a C-machine could always receive signals via sensors that would permit it to know that it was testing itself - reviving the A-irrelevance claim on CASP ...
- Let's say you were correct about this ("P can't be permitted to figure out that it's testing itself"), for the sake of argument. The HaltingProblem, however, is about figuring out whether any and all programs halt -- it was never claimed that it can't be solved for some programs. So say you've got a program P, which, if allowed to figure out it is testing itself, can solve the HaltingProblem when given itself as input: P(P). Ok. Now take modified program P' which cannot test to see whether it tests itself. You appear to agree that P'(P') fails to solve the HaltingProblem. But then your other program, P, will fail to resolve the HaltingProblem when given P(P'(P')) -- and P' is not P, so the notion of seeing whether it is testing itself or not is of no help in any case. -- Doug
- While my latter statement was informal, if I have some modified P'(P') my very clever P can ascertain what's going on with its modification by exactly the same logic as P(Q(Q)). In fact, my P is so clever I'm going to give it a new letter just so we don't confuse it with any old P. Let's see ... how about D, in honour of DougMerritt, the man who used it to prove that LC is not TuringEquivalent?
  - Nope, didn't prove that, didn't say that, don't believe it. -- DougMerritt
  - If it will please you, and since deleting ThreadMess usually displeases you I'm asking before doing, I'll delete those portions of this text where I refer to such an inference on the conclusions you did draw. -- Pete
- Peter was onto something, because the construction of Q in "popularization of science" books was rather informal (along the lines Q invokes P and then takes the opposite decision (to halt or not to halt). This is rather sloppy, because for a particular program P the construction of Q fails to provide the counter-example. Imagine if we're inside Java (and I saw Java and C based sketches of the proof that fail to consider this), and Q invokes P and then P tests to see if the stack depth is greater than 1 and it does the trick suggested by Peter if so. That means the sketch of a proof fails to give a correct algorithm for deriving Q from P.
- But then the trivial technical trick that solves the problem in the naive construction of Q. Rather then calling P directly, Q constructs a Java (or C, or Scheme, or TM, etc) interpreter, and thus runs P inside the interpreter, for which purpose now P can see that it's running top-level. So now the inner instance of P cannot do the trick, and thus the outer instance is condemned to fail to decide correctly the outcome of Q. Thus the pseudo-code for q becomes

 (define q (if (scheme_interpreter '(p q)) 
                  (loop-forever)
                   #t))

And therefore now there is no programmer distinguishable difference between the outer top level (p q) and the inner (p q). Sorry, Peter, now the Nobel has to wait a little bit. -- CostinCozianu
- As I said to Doug, I don't buy this in the TM construction; P can always drop down to the tape and analyze it bit by bit to figure out what the whole of Q is doing. LC prevents this exformally, so closes the barn door before the horse has bolted. -- Pete
- Again, the inner instance of (p q) is run inside an interpreter. So it cannot analyze the "whole tape" that is really running the show, but only the virtual tape that it is offered to it by the interpreter. And then no matter what decision it takes, with the sole condition that it is deterministic, even if P has the knowledge that it's analyzing exactly the Q that he knows in advance, Q will take the opposite decision, and P is in a lose-lose situation. The only way P could try to avoid the defeat was if it could distinguish the situation when it's running inside Q or when it's being run from the "top-level" (so to speak). But then Q by running P inside an interpreter made the two situations undistinguishable. So whatever decision you take, even knowing in advance the Q that I'm going to write, you're doomed to give bad results.
- As a proof of that, given the generation of the Q above (it really should eb a Scheme macro, but you get the drill) try to write a program P that decides not the halting of all programs, but just of the program Q that will be derived from P itself. You won't be able to write it. Because if you return "TRUE" you'll return TRUE both from the top level and from inside Q, and then my Q will not halt. And if you return false, my Q will halt. Replace a Scheme interpreter written in Scheme with a TM interpreter written in TM and you get the same effect. -- Costin
- Yes, quite right, this would sink it on the TM, if you could prove you had an interpreter that can't be cracked. And not on a C-Machine where each P can employ sensors that observe its situation. -- Pete, before thinking harder below, for which see the stuff below the next horizontal line. Damn WikiBase poops out after 4 levels of indent.
- Possibly on the C-machine, but then your argument becomes mystico-metaphysical. P is no longer a program (or mathematical formalism) but a machine connected intrinsically to the reality surrounding it, a sentient physical entity.
- Ability to sense does not imply sentient. All our computers are C-machines, and that's sufficient to bollocks up the notion that they can't solve halting for C-machines. Naturally the opportunity to solve halting does not imply the ability to solve halting. No more than the opportunity to walk implies the ability to walk. Our C-machines are horribly handicapped by the VonNeumannArchitecture ...
- That would be truly deserving a Nobel prize, but you have to construct it first. Don't hurry though, we're patient :) In the meantime, for all practical purposes we're stuck with ChurchTuringThesis.
- You misunderstand the point made here. A C-machine P ("CP"), by deploying sensors that permit it to distinguish its situation with respect to Q, could perform the feat quoted in my first para above. Therefore a C-machine not limited by Turing's A-machine computability results: they are irrelevant to C-Machines. -- Pete
- I don't see how you think you've established that. On the other hand, if you really believe that, then go ahead and build such a machine. If your claim for it is true, there are certainly commercial applications, never mind jokes about Nobel Prizes. -- Doug
- As I said it's trivially demonstrated that if CP can inspect itself as it runs it can make the distinction about whether it is running as the inner or outer invocation.
- Nope, not demonstrated at all, let alone "trivially" -- DougMerritt
- [[Not only that, but more importantly, again (sigh) it is irrelevant whether or not CP can make this distinction, because a CP that has the opportunity to do such an inspection is not allowed to run in what you call the "inner invocation". Running there is merely a version of CP in a pristine environment with no information provided to it except its own original input and its own resources, as by its very definition it must be able to do. There is no way this version of CP can tell who has called it or what its caller is trying to accomplish. It must simply go ahead and "solve" the Halting Problem as best it can (which is not going to be good enough, of course).]]

In any case, you guys can quit your crowing on the A-machine. Costin is, above, assuming the existence of an interpreter that can't be cracked. Let's call it I. If you'll kindly refer me to a proof that such an interpreter can exist, then you're out of the woods. To forestall the usual squawking, no, I don't know that you can't prove such a thing - but the burden of proof remains with you. It sure doesn't smell recursive ... -- Pete

Ahem, I beg to differ, Pete. If we restrict the discussion to a purely functional subset of Scheme, then such interpreters of a functional subset of Scheme are written by students around the globe all the time. That they cannot be "broken" follows trivially from the semantic of Scheme: if all the primitives (car,cdr, define, let, if` etc) are deterministic, and all the composition constructs are deterministic, it follows by structural induction that all constructed procedures are deterministic so that evaluating the same expression in any correctly implemented interpreter will always yield the same result.

In principle, of course, I agree. Or else I would have popped up a counter-example. But a specification is not a proof; you'll need to start by proving that each of these primitives cannot be cracked, then show that their principal of combination cannot be cracked. Given RicesTheorem (http://mathworld.wolfram.com/RicesTheorem.html) this is not a trivial undertaking. At each step you risk the AntecedentAssumedFallacy. This is why I say the uncrackable interpreter smells non-recursive.

For one thing, your conclusion is incorrect. CC's argument is in fact straightforward, trivially so, so Rice's Theorem doesn't have anything really to do with it. Secondly, this is really ironic, because in fact Rice's Theorem can be used to prove the various points CC and I have been trying to make. It is one of the many results that is essentially equivalent to the HaltingTheorem and Goedel's theorem.
Yes, that's exactly why I was warning CC against the antecedent being assumed. If Rice's theorem is based on halting, and Rice's theorem were to apply to the rudiments of the interpreter CC wanted to prove halting, then a pickle occurs. Like CC, I'm not going there - life's too short!
This is amusing considering the conversation, and somehow I suspect it won't help, but nonetheless see http://users.informatik.haw-hamburg.de/~owsnicki/rice.html. -- DougMerritt

Mapping from a purely functional subset of scheme to lambda calculus is also a beaten path, so if you want a full-blown interpreter to be presented to you as part of the proof, you'd better give us some good reason rather than asserting the burden of proof on the other side. Because it's surely boring to write down that interpreter and it provides no insight into the HaltingProblem whatsoever. A quick reference could be SiCp, but examples of such interpreters are so many, I don't know where to begin.

I don't actually expect you do any such thing. It sounds like a frightful waste of time. But until you or someone does, the A-machine version of the halting problem remains cracked. And then as Doug points out most likely TM != LC.

Damnit, stop saying that, I never claimed that, and I don't believe it (also CC just said the opposite at bottom of page), and the only reason I didn't contradict you last time you claimed I said that is that I get tired of contradicting every single thing you say on these topics. But for the record, please, do not speak for me again on these topics, because we are in massive disagreement, with no sign of reaching consensus on even the smallest of issues. -- DougMerritt
Well, we agree on that anyway ;-) -- Pete
Just as a btw, there's the nice and simple SIOD -- Scheme In One Defun -- not that I'm going to waste effort in that direction. -- DougMerritt
You know, speaking purely as an old Prolog guy, you're really beginning to make me feel like I was missing out on something when I didn't learn Scheme ...

P.S. it's great to try to figure out a way to beat the system, but you should be a little less convinced that any particular brainstorm has already succeeded.
Um, that's the humor part.

I usually read my email on Tuesdays. Please have the Nobel committee bear this in mind.
- [Although it depends very much on the kind of non-determinism and class of machine; there are many possibilities.]
- Not certain how the construction here depends on non-determinism and class of machine - this sally self-consciously restricts itself to the A-machine.
- [I was commenting on CC's sentence, "If we allow for non-determinism, then, yes, you can make a program P that ..." -- in other words, although CC is right, the operative word there is can, as in, under some circumstances, with some kinds of non-determinism, with some kinds of machines. It is not the case that any old kind of non-determinism, with any old kind of machine, gives that power. -- Doug]

There's a valid conclusion to be drawn that maybe TM are not as good as real computers (those can do all kinds of non-deterministic tricks, like being connected through networks, running MS Windows, or using non-ECC memory :) ), but then the stuff that we need TM for can be adequately modeled using TM.

Even more serious than CC's critique: there's no Nobel prize in math. There's the Field's medal, but you may be a bit long in the tooth for that.

Yes, apparently a mathematician raced off Nobel's wife. Strange thing, science ;-)

FYI this rumor has been endlessly investigated, and there appears to be no supporting evidence for it at all, it seems to simply be a colorful urban legend. As such, it's a good one to repeat at parties, but it's nice to know when one is repeating a myth. :-)
I didn't know. Anyway let's just re-express the above results in a DNA computer and have them give us the prizes for chemistry and biology. Which one do you want? Whichever, that's the one that I want.

Keep in mind that Turing's original machines are far from the only model of computation ever studied. Machines with oracles are non-deterministic, for instance, and there are also randomized machines, which do indeed have different performance. For instance, the computational complexity of some algorithms depends on whether the Extended Riemann Hypothesis is true, which no one knows is true or not - however, such algorithms can typically be converted into the faster computational class simply by using randomness, which doesn't exist in the original Turing machines. It's a pretty big topic, and TuringMachines are simply a starting place. -- Doug

The most fundamental plank of ComputerScience is the General HaltingProblem. Unfortunately there appears to be a problem with the GHP, as follows:

I have here the code for a program, P, that can tell you whether any program halts or not for given input data.
I construct a program Q based on P which, if P says its input program doesn't halt, immediately halts, and if P says the program halts, goes into an infinite loop.
Feeding Q(Q) to P I can see that if P says it halts, it won't, and if P says it doesn't halt, it will.

Therefore,

I don't have any such program P and anyone else who says they do is full of it.

But:

If I don't have any such program P then there's no way I can construct the derivative work Q.
Since the proof of P's non-existence requires me to feed Q(Q) to P, which I can't do without Q, then I can't prove P's non-existence. In effect, the proof is subject to a subtle AntecedentAssumedFallacy.
Most likely all we've proved is that a program P must be smart enough to recognize its own algorithm, and then output a third result, to wit, that the halting behavior of the input depends on its output.

Realizing this, it's plain that the whole form of the proof is identical with the convict's invalid reasoning in the UnexpectedExecutionParadox. All the computability results that rest on the GHP are therefore null and void, and we better start over on this topic. Oh, another Nobel for me? Pesky things, I keep tripping over 'em. -- PeterMerel

I can't quite tell whether this is a joke or not. Assuming it's serious (DeleteMe if it's just a joke): There is no fallacy. Here's one way to adjust the proof that may make it clearer that there is no fallacy.

Consider any program P. It needn't be a halting tester.
Define a new program Q, which passes itself as input to P, runs P, and (a) returns immediately if P returns 0, (b) goes into an infinite loop if P returns 1, and (c) does anything you like if P doesn't halt or doesn't return a single value that's either 0 or 1.
Observe, trivially, that if you feed Q to P then P doesn't return 0 if Q fails to halt and doesn't return 1 if Q halts.
- Um, did you mean to feed Q to Q? Obviously if P is any program it is free to do act however it likes, including returning 0 if Q fails to halt, and returning 1 if Q halts - right? Nope, I meant what I said. See below.
Now consider the statement "For any inputless program R, feeding R into P yields 1 if R halts and 0 if it doesn't".
That statement is false, because what it asserts of all inputless programs isn't true for the particular inputless program Q.

Hence, we've shown that no program P can be a halting tester in the precise sense described by that statement. And we haven't had to assume that any program is a halting tester in order to do it. We started with any candidate program, and produced a new program for which it doesn't give the right answer. -- GarethMcCaughan

I expected this semi-humorous argument to go down in flames, but couldn't quite put my finger on why just yet. Anyway you're quite right, many thanks. A more serious if exformal objection is raised on WhatDoesHaltingMean and discussed on GeneralHaltingProblemProblemProblem, suggesting that InfiniteLooping is in fact exactly what halting means. Ergo Q can not fail to halt, and the Turing fence is down again ... -- PeterMerel

The clearest technical book on the subject that I've ever seen is The Language of Machines - An introduction to Computability and Formal Languages by Floyd and Beigel, ISBN 0716782669 . Obviously, these things cannot be adequately covered non-technically/non-mathematically. -- DougMerritt

Here's a program (in an imaginary language, for an imaginary machine) that might explicate things.

 # ALLEGED_TESTER is a function which accepts a single argument.
 # We return a new function F that proves that ALLEGED_TESTER isn't
 # a perfect termination tester: in other words, either F terminates
 # and ALLEGED_TESTER(F) doesn't return 1, or else F doesn't terminate
 # and ALLEGED_TESTER(F) doesn't return 0.
 def thing_not_tested_validly(alleged_tester):
   def f():
     tester_result = alleged_tester(f)         # same f as we're now defining
     if tester_result == 1 then loop_forever()
     return
   return f

Proving the assertions in the comments there is easy. If ALLEGED_TESTER(F) returns 1 then F loops for ever. If ALLEGED_TESTER(F) returns something other than 1 then F doesn't loop for ever.

If you're bothered by the "same f as we're now defining" thing, don't be: there are ways of working round that. But this is one of the subtle points of the proof. -- GarethMcCaughan

What is wrong with the first proof? It's proof by reductio ad absurdum. To prove that P can't exist you assume P does exist and make it lead to a false conclusion, given your knowledge base.

If you do away with this kind of proof you do away not just with the GHP but with most of mathematics too. :-)

Nothing is wrong with it. I provided the second one because I thought it might evade some mental blocks. It might be worth mentioning that a similar thing can be done to many proofs by reductio ad absurdum, for the sake of those who find RAA hard to trust. -- GarethMcCaughan

Let me know if I get this:

We have some program Q.
We have some other program P that when fed some program tells if that program terminates or not.
Q is a program that feeds itself as input to P and then runs P.
When P terminates, if P says Q halts then Q goes into an infinite loop, else, if P says Q doesn't halt, Q exits.

Nice...

What this is really telling me is that there's no way to actually completely test a program except by running it. -- CristiOpris

Yes, that's the idea. It's a proof that actually we don't have a program P that tells whether things terminate or not. And it's even worse than you say :-), because even running a program can't prove that it doesn't terminate. -- GarethMcCaughan

Yes, the "general halting problem" proof is one that is commonly given in college courses. (At least it was in the early '80s. ;-)

But I think it's flawed.

Briefly, to know if Q halts, you need to know its input. Its input is Q, but to know if that Q halts, you need to know its input. So, you're really testing this:

  Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q(Q( ... ))))))))))))))))))))))))

Where there's an infinite number of Qs.

The definition of the thing you wish to run doesn't halt, so you can never get to the point of running it. -- JeffGrigg

Ahhh, yes: THAT is the approach I was looking for. Thanks, Jeff! -- TomStambaugh

No, what you input to Q is the "source code" of Q, so no need to get all recursive here.

No, there's no way to know if a program will halt or not unless you know the input. Consider this program: { if input = "halt" then halt else loop_forever } Now, does it halt or run forever? You can't know if it halts unless you know if the input is "halt".

So, to evaluate if Q halts, you have to know its input halts. That input would be Q, so...

Yes, but the input to Q is not the result of executing Q, it's nothing at all. Here's a slightly reworded definition that makes that a little clearer:

program P(source, input) = { if source_code_will_terminate(source, input) then return 'halts' else return 'loops' }
program Q() = { execute P with (source = source of Q, input = null); if result is 'halts' then infinite_loop }
The call to P inside Q is trying to work out if running Q with no input data will halt or not.
Therefore running Q with no input data will halt if running Q with no input data doesn't halt, and loop if running Q with no input data halts. This is clearly a paradox.
The only way to resolve this paradox is to assert that source_code_will_terminate doesn't know what the hell it is talking about.

-- GavinLambert

I think the problem might be relating to the definition of 'input'. I'd say that, although there is no explicit input to 'Q()' (according to the signature), there is an implicit input, in the form of the call to 'P' ('Q' asks for input from 'P'). With that call, 'P' ends up having to analyse itself with the associate input of 'Q'... and now we've got a problem.

As an aside, there would seem to be no reason that 'Q' couldn't detect the situation, that it has processed itself multiple times, or even processed itself at all, and therefore respond to the question with a question, so to speak: "Does 'Q' halt? I don't know... do you want it to halt?"

-- WilliamUnderwood

OK, so suppose we have this program "R" which can analyze an input and halts if the input is equivalent to itself...

"Does 'Q' halt? I don't know..." Well if 'P' doesn't know then it isn't solving the halting problem. If you ask the question "does this program halts?" and for some programs like 'Q' you are forced to answer something else than 'yes' or 'no', then Turing is right: you cannot write a program which can answer that question with a 'yes' or 'no' for any given input program. -- Samuel Gélineau

To break down what I see as the problem here, at least on the top part of the page, the proof is this: "Even if you had a halting predictor, you don't have a halting predictor. I can do this for all putative halting predicters." To put something else in that form, "Even if you think you have an integer that is greater then all others, I can prove that your integer isn't greater then all others (by simply adding 1 to yours). I can do this for all putative largest integers."

Your inability to produce the integer that is greater then all others isn't a problem. I never really depended on your specific integer, I made a statement about all of them, by showing concretely that each and every one of them is inadequate. -- JeremyBowers

Hmm...

Assuming that a program could be defined which can recognize itself as input:

From any halting detector, you can provide a program which halts or not based on the opposite of the decision of that detector.

And for any such program you provide me which does that, I can provide a program which can detect trickery of that specific nature.

We can't solve the halting problem in general, but we can get as close as we'd like.

Now, "Can this result be made useful?" is a completely different question.

-- WilliamUnderwood

P.S., where n = the biggest number you can quote to me, the number returned by (n+1) is the largest integer. Prove me otherwise :p (n+1)+1 - I don't think you really understand mathematical symbology. Anything goes in those variables, not just pure numbers.

It is well known that it is, on the other hand, feasible to solve the halting problem for all machines up to size K, for any given finite constant K you care to name. The machine that solves that particular finite K-halting problem will be bigger than K (O(2^K) does it nicely). Unsurprisingly, the class of machines it can solve does not, therefore, include itself. -- dm

Hence the answer of "I don't know. Find a bigger machine." :)

Also, yes, it is useful. Many proof techniques are based on exhaustive examination of state space for things that are equivalent to solving the halting problem. Since the state space is finite, it is sometimes feasible, whereas in the general case it clearly isn't. This is another critical thing to understand about the Halting Problem non-Problem: It specifically refers to the general case, and does not apply in less general cases. Though even in the less general cases it does tend to imply an irreducible exponential cost. -- JeremyBowers

Why need a "Halting Predictor" to prove the point...

How about "Is it possible to predict the output of the function f(int i){return i;}"? The function takes an int (let's say only 0 or 1) and spits it out. It is not possible to tell exactly what it spits out, whether a 0 or a 1 (without knowing the input). Doesn't this qualify as a "proof" that it is not possible to predict the output? If NO (it doesn't qualify), then how different is the "Halting Problem" from this one other than to disguise the input and output in some fancy programmer's formalism? -- Mohyneen Mehdi

You don't necessarily need something fancier, but you do need to consider all possibilities one way or another. You're basically assuming the result you want to prove; that's why this is not a proof.

Maybe I am missing something or maybe I am not, but I can't give in to the "circular reasoning" that lurks in the proof of the Halting Problem. In standard English, the solution goes like this... P has the task of predicting Q's output (or behavior). But Q has the final say in the matter and waits till P makes its prediction, after which Q conveniently adapts its behavior only to violate that prediction.

So, as I see it, P has to look at "Q AND Q's Input" in order to predict its behavior (or output). But Q's INPUT is P's OUTPUT. So, effectively, P has to look at "Q AND P's OUTPUT". But P's OUTPUT is obtained only by looking at "Q AND Q's Input". Back to square one! It's important to understand that by Q's INPUT I don't mean Q's parameter values; I mean information that Q eventually uses to behave the way it does.

P needs information which is obtained from Q, who in turn needs the "same" information from P. But according to the proof, that information is generated on the fly and P is given the credit (or discredit) for generating it. That information (i.e the prediction P makes) couldn't have been generated because P doesn't know Q's complete Input information, information which can come only AFTER P makes it's prediction (i.e the prediction itself).

Where exactly am I going wrong?

-- Mohyneen Mehdi

Here's how I see it: Q's input doesn't have to be a precalculated boolean value equal to P's output. P is supposed to (among other things) look at its own source code and figure out for himself what P's output is supposed to be. If P wants to execute this code in order to find out then P will loop forever, won't ever give an answer for this particular program, and cannot solve the HaltingProblem in general. If P chooses to guess Q's input without executing its own source code, then whatever his guess will be he will give a wrong final answer about Q, so P still isn't solving the HaltingProblem in all cases. -- Samuel Gélineau

Where exactly am I going wrong?

There's several common spots of confusion. Maybe you can help us re-state or otherwise explain the problem so it's less confusing. (But I don't think there's any way of getting around the contradiction, since it's a proof-by-contradiction.) Confusion between what people mean by Q:

the source code, a string like "int f(int i){return ~i;}".
the running executable, which either returns with its final result (halts), or gets stuck in an infinite loop (doesn't halt).
the actual result returned by the executable.

Other people are mislead into

thinking of Q and P as unique, singular things - thinking that there's only 2 things, each of them has to make a decision, and so one of them must make the decision first.

The same sorts of confusion have led many people to claim that QuinePrograms are impossible, when clearly several do exist.

Also, a few of the "proofs" of FreeWill seem to be based on the same confusion.

P needs information which is obtained from Q, who in turn needs the "same" information from P.

Yes, sort of. When P runs, it inspects the source code for Q, and also inspects the input that will be fed to Q.

Please note that P does not actually call() or eval() or execute Q. (Although the sorts of analysis it does are probably very similar to the sorts of analysis that go on when the compiler compiles and partially evaluates Q when we later compile Q).

But according to the proof, that information is generated on the fly and P is given the credit (or discredit) for generating it.

Yes, exactly.

That information (i.e the prediction P makes) couldn't have been generated because P doesn't know Q's complete Input information, information which can come only AFTER P makes it's prediction (i.e the prediction itself).

I think you're very close to understanding the HaltingProblem.

In this case, P *does* know Q's complete input information. Tell me the source code to P (long before you ever *compile* P), and I can tell you the long string that makes up Q's complete input information. It is, in fact, the source code to Q (which includes a copy of the source code to P that you gave me).

Say I want to know whether this function halts (i.e., whether it is an algorithm), and if so what value it returns:

  int count_apples(){
    int left = count_apples_on_left();
    int right = count_apples_on_right();
    return( left + right );
  }

By "input", we normally mean input from *outside* the computer. The value returned by count_apples_on_left() does *not* count as "input". I inspect that function and see that it calculates a value without any input from *outside* the computer. Say I run count_apples_on_left() once and it returns "17". I can be confident that it will return "17" every time I or anyone else runs that subroutine. Right?

So, what does count_apples() return? Or does it never halt?

I inspect count_apples_on_right(), and I see that it reads in 2 characters from standard input. Those 2 characters count as "input", not just to count_apples_on_right(), but to any program that calls it (such as count_apples() ), and to any program that indirectly calls it (perhaps by calling count_apples() ).

If I know what those 2 characters will be, do I have any hope of figuring out the output of count_apples()?

I just came to read here; correct me if I misunderstood something.

For halting property, there are three kind of program.

Program that always halts.
Program that always does not halt.
Program that halts on some input and not on other. Let's called it "Conditionally halt"

Halting problem states that (I took this from first line in HaltingProblem)

"It is impossible to write a program that runs in finite time that is able to decide whether an arbitrary program will halt (with a certain input)."

Let P be the halt tester program, and Q be the program that will be feed to P, and go in infinite if P return "Q will halt", and halt if P says "Q never halts"

Now the statement With a certain input is where the flawed is.

What is the input to first Q that is fed to P?

''The input is empty, or a dummy string, it does not matter at all. As a matter of fact you can consider the input to be part of the program, and that settles all the useless discussion about input. You cannot define a program P that decides for all programs if they halt with an empty input.The counter-example Q defined by

   (define (Q) (if (eval '(P Q)) (loopforever) true))

settles it. If you notice, Q does not use any input at all. So the input can be anything, it's better left out of the picture.

Technically Q is often constructed along the lines

  (define (Q X)  (if (P X X) (loopforever) true))

And the counter-example is that P cannot decide for

 (P Q Q)

Which is more faithful to the original formulation of the halting problem where P had to have 2 arguments (P X I) where X is the program and I is the input. But this later arrangement, while valid, makes it less intuitive, as the reader is distracted by the artifice of using Q both as program and input, and by the role of the dummy variable X in the body of Q. So reducing the problem to programs with empty input, makes the intuition much more accessible. So we prove that we cannot even construct a program that decides the termination of all programs with an empty input.

I took the liberty to delete the flawed discussion about the lookup tables, and the relative sizes of programs and lookup tables. It just distracts from a technically trivial proof. -- CostinCozianu

I don't see why you did so. I said explicitly that it was the starting place for one of the classic approaches to proofs, which I was trying to lead up to one step at a time - maybe not one of the proofs that you prefer, but I don't see why that's reason to delete it. It's possible that your explanation will be better understood by the current audience, but even that is hard to say - obviously, many people do not find the topic clear even when I think it's clearly presented (and yes, I think your statements are clear). I mean, I do see your point that the topic should be simpler, the way you presented it; the question is, will your audience get it. If they do, cool. -- DougMerritt''

I just reread the above and I see specifically what was subconsciously bothering me. I do not think you were clear in the critical part, the conclusion: "And the counter-example is that P cannot decide for (P Q Q)". I think you need to do something to make that much more glaringly obvious, or else your "simplified" approach won't get the point across. -- Doug

But that was exactly the point: that if we discuss about a program/procedure say P2 that takes 2 parameters: (P2 X I), we make it far less obvious to come up with (Q2 X) that evals (P2 X X) and turns the result on its head. Instead if we focus just on P1 that takes input a program that runs with an empty (or otherwise fixed) input then we construct Q1 that evaluates (P1 Q1) and turns it on its head. So assuming a purely functional subset of Scheme, the proof is:

 ;Proof 1
 ;assume there is a P1 that decide termination for procedures with no parameters
  (define (P1 X) (...))
 ;where  forall X, (P1 X) evaluates true if (X) halts, false otherwise [1]
 ;construct the function with no parameter 
  (define (Q1) (if (eval '(P1 Q1)) (loopforever) true)) ;[QDEF]
 ; then 
 ;  if (P1 Q1) evaluates to true, it follows according to [QDEF] that (Q1) loops forever , contradicting [1] --  -- {step A}
 ;  if (P1 Q1) evaluates to false, it follows according to the definition of Q1 that (Q1) terminates , contradicting [1] -- [step B]
 ; therefore because (P1 Q1) cannot evaluate to either true or false without contradicting [1]
 ; the assumption that there exists P1 leads to a contradiction and is therefore false (reductio ad absurdum)

This is the complete sketch of the proof about the non-existence of a Scheme procedure P1 that can decide for all Scheme procedures with no argument if they terminate or not. Using code in a real language makes it easier to follow, while keeping it reasonably formal. If on the other hand we try to prove the version with (P2 X I), coming up with [QDEF] and verifying [step A] and [step B] is less intuitive:

 ;Proof 2
 ;assume there is a P2 that decide termination for procedures with one parameter ("input")
  (define (P2 X I) (...))
 ;where  forall X, (P2 X I) evaluates true if (X I) halts, false otherwise [1]
 ;construct the procedure with one parameter 
  (define (Q2 R) (if (eval '(P2 R R)) (loopforever) true)) ;[QDEF]
 ; then 
 ;  if (P2 Q2 Q2) evaluates to true, it follows according to [QDEF] that (Q2 Q2) loops forever, contradicting [1] -- [step A]
 ;  if (P2 Q2 Q2) evaluates to false, it follows according to the definition of Q2 that (Q2 Q2) terminates, contradicting [1] -- [step B]
 ; therefore because (P2 Q2 Q2) cannot evaluate to either true or false without contradicting [1]
 ; the assumption that there exists P1 leads to a contradiction and is therefore false (reductio ad absurdum)

So I think that it is clear that Proof 2 is both harder to follow and harder to remember at a later time than Proof 1, and this responds directly top the anonymous contributor's question as to what happened with the input for Q. There is no input, and I presented the justification why it is better to look at the version with no input.

Now for GoldPlating we can tighten some details by to replacing recursion with a fixed-point combinator to make the proof adequate for the halting problem within LambdaCalculus {there's no lambda expression P so that for any other lambda expression X the application (P X) reduces to "true" (aka (lambda (x y) x) ) if X has normal form, and to "false" if X doesn't have a normal form }. Because LC and TM are known to be computationally equivalent this is as good as a proof of the halting problem for TM.

BeingRefactored? See HaltingProblemDiscussions

Potential New Pages:

TheHaltingProblem?
- description of what the problem is.
- HaltingProblemAlgorithms?
- HaltingProblemDiscussions
- what else

See http://ebiquity.umbc.edu/blogger/2008/01/19/how-dr-suess-would-prove-the-halting-problem-undecidable/ for a really understandable, and funny halting problem proof.

CategoryProof CategoryCoding