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:

    Conscience was the barmaid of the Victorian soul. Recognizing that human beings were fallible and that their failings, though regrettable, must be humoured, conscience would permit, rather ungraciously perhaps, the indulgence of a number of carefully selected desires.
    —C.E.M. (Cyril Edwin Mitchinson)

    It is characteristic of the epistemological tradition to present us with partial scenarios and then to demand whole or categorical answers as it were.
    Avrum Stroll (b. 1921)

    The anorexic prefigures this culture in rather a poetic fashion by trying to keep it at bay. He refuses lack. He says: I lack nothing, therefore I shall not eat. With the overweight person, it is the opposite: he refuses fullness, repletion. He says, I lack everything, so I will eat anything at all. The anorexic staves off lack by emptiness, the overweight person staves off fullness by excess. Both are homeopathic final solutions, solutions by extermination.
    Jean Baudrillard (b. 1929)