Halting Problem - Recognizing Partial Solutions

Recognizing Partial Solutions

There are many programs that either return a correct answer to the halting problem or do not return an answer at all. If it were possible to decide whether any given program gives only correct answers, one might hope to collect a large number of such programs and run them in parallel, in the hope of being able to determine whether any programs halt. Curiously, recognizing such partial halting solvers (PHS) is just as hard as the halting problem itself.

Suppose someone claims that program PHSR is a partial halting solver recognizer. Construct a program H:

input a program P X := "input Q. if Q = P output 'halts' else loop forever" run PHSR with X as input

If PHSR recognizes the constructed program X as a partial halting solver, that means that P, the only input for which X produces a result, halts. If PHSR fails to recognize X, then it must be because P does not halt. Therefore H can decide whether an arbitrary program P halts; it solves the halting problem. Since this is impossible, the program PHSR could not have been a partial halting solver recognizer as claimed. Therefore, no program can be a complete partial halting solver recognizer.

Another example, HT, of a Turing machine which gives correct answers only for some instances of the halting problem can be described by the requirements that, if HT is started scanning a field which carries the first of a finite string of a consecutive "1"s, followed by one field with symbol "0" (i. e. a blank field), and followed in turn by a finite string of i consecutive "1"s, on an otherwise blank tape, then:

  • HT halts for any such starting state, i. e. for any input of finite positive integers a and i;
  • HT halts on a completely blank tape if and only if the Turing machine represented by a does not halt when given the starting state and input represented by i; and
  • HT halts on a nonblank tape, scanning an appropriate field (which however does not necessarily carry the symbol "1") if and only if the Turing machine represented by a does halt when given the starting state and input represented by i. In this case, the final state in which HT halted (contents of the tape, and field being scanned) shall be equal to some particular intermediate state which the Turing machine represented by a attains when given the starting state and input represented by i; or, if all those intermediate states (including the starting state represented by i) leave the tape blank, then the final state in which HT halted shall be scanning a "1" on an otherwise blank tape.

While its existence has not been refuted (essentially: because there's no Turing machine which would halt only if started on a blank tape), such a Turing machine HT would solve the halting problem only partially either (because it doesn't necessarily scan the symbol "1" in the final state, if the Turing machine represented by a does halt when given the starting state and input represented by i, as explicit statements of the halting problem for Turing machines may require).

Read more about this topic:  Halting Problem

Famous quotes containing the words recognizing, partial and/or solutions:

    “The world is never the same as it was.... And that’s as it should be. Every generation has the obligation to make the preceding generation irrelevant. It happens in little ways: no longer knowing the names of bands or even recognizing their sounds of music; no longer implicitly understanding life’s rules: wearing plaid Bermuda shorts to the grocery and not giving it another thought.”
    —Jim Shahin (20th century)

    “The one-eyed man will be King in the country of the blind only if he arrives there in full possession of his partial faculties—that is, providing he is perfectly aware of the precise nature of sight and does not confuse it with second sight ... nor with madness.”
    —Angela Carter (1940–1992)

    “Football strategy does not originate in a scrimmage: it is useless to expect solutions in a political compaign.”
    —Walter Lippmann (1889–1974)