From: ld231782@LANCE.ColoState.Edu (L. Detweiler)
Newsgroups: comp.theory,sci.math
Subject: Turing's Halting problem revisited
Date: 9 Oct 92 02:01:43 GMT
Organization: Colorado State University, Fort Collins, CO  80523


- - -

This is an opportunity to recast Turing's proof in concise form with some
convenient notation.

tolman%asylum.cs.utah.edu@cs.utah.edu:

>  Let us suppose we construct a Turing machine which will solve the halting
>problem.  It is special in that it recognizes its own coding sequence, and
>stops with a special output character when it sees its own sequence.  This
>Turing machine is not susceptible to the self reference paradox which
>normally kills it.

fischer-michael@cs.yale.edu:

>By hypothesis, your machine M_e has the following property:
>    M_e(x) = 2 if x = e
>    M_e(x) = 1 if M_x(x) halts and x <> e
>    M_e(x) = 0 if M_x(x) does not halt and x <> e
>Using M_e, I can construct a new machine M' which does the following:
>    M'(x) = 0 if M_x(x) does not halt
>    M'(x) runs forever if M_x(x) halts
>(Note that M'(e) runs forever since M_e(e) halts.)

A `standard' halting algorithm ideally would be in the form

H(x,y) = 0 if x(y) hangs
H(x,y) = 1 if x(y) halts

A version of Turing's proof proceeds by defining

H2(x) halts if H(x,x) = 0
H2(x) hangs if H(x,x) = 1

With H2 the encoding of this machine, the contradiction emerges from testing
the putative halting algorithm H on input H2,H2.  By the definition of H,

H(H2,H2) = 0 if H2(H2) hangs
H(H2,H2) = 1 if H2(H2) halts

By the definition of H2,

H2(H2) halts iff H(H2,H2) = 0
H2(H2) hangs iff H(H2,H2) = 1

Substituting above,

H(H2,H2) = 0 if H(H2,H2) = 1
H(H2,H2) = 1 if H(H2,H2) = 0

Since for all x and y, H(x,y) = 0 or H(x,y) = 1, this is manifestly a
contradiction!  This is Turing's famous conclusion of the nonexistence of
a machine H(x,y) that solves the `halting problem'.

- - -

Another form that is more exact but less simple uses `x?' as the encoding 
of machine `x' and `y!' as the machine simulated from its encoding 'y'.  
These are inverses in the sense that (x?)!(y) = x(y) for all y, or more 
conveniently written, x?! = x.  More precisely then,

H(x,y) = 0 if x!(y) hangs
H(x,y) = 1 if x!(y) halts

The contradiction emerges from considering H(H2?,H2?).  Note that H2(H?)
also leads to a similar contradiction (a machine that hangs if it halts and
halts if it hangs).

- - -

In response to the original poster's query, suppose the demand on H(x,y) is
less constraining:

H'(x,y) = 2 if x = y, otherwise
H'(x,y) = 0 if x(y) hangs
H'(x,y) = 1 if x(y) halts

Define H2'(x) similarly:

H2'(x) halts if H'(x,x) = 0
H2'(x) hangs if H'(x,x) = 1

Paralleling the derivation above,

H'(H2',H2') = 0 if H'(H2',H2') = 1
H'(H2',H2') = 1 if H'(H2',H2') = 0

But here it is NOT the case that for all x and y, H'(x,y) = 0 or H'(x,y) = 1.
In fact, by definition, H'(H2',H2') = 2!

- - -

H(x,y) surely does not exist, and perhaps neither does H'(x,y).  However,
the `halting problem' is so important that an algorithm even for restricted
inputs could potentially resolve many currently unsolved problems.  Hence, 
let

H2(x,y) = 2 if [...]
H2(x,y) = 0 if x(y) hangs
H2(x,y) = 1 if x(y) halts

What is the least restrictive filter [...] such that H2(x,y) exists?

- - -

Other approaches to `solving' the halting problem (or at least avoiding
Turing's contradiction) besides H2(x,y) are conceivable.  One possibility
is that there are other computational processes besides those modelled by
Turing machines.  The position of the famous `Church-Turing thesis' and
widely-held conventional wisdom is that this is not the case.  Nevertheless,
if such machines exist, they might be modelled by new axioms describing their
behavior.

Suppose, in addition to the axioms that model Turing machines,

(a) the encoding of a machine does NOT EXIST INDEPENDENT OF ITS INPUT 

or equivalently

(b) the encoding of a machine is DEPENDENT ON ITS INPUT

A crucial step in Turing's proof above requires finding the encoding of H
(or equally H2 by above) independent of its input, i.e. H(x,y) and H2(x)
are defined and H? and H2? then assumed to exist.  Under the new axiom (a)
this assumption is false.

(a) may seem like an arbitrary, artificial restriction. To the contrary, it 
models exactly an intuitive and familiar class: the encodings of Turing
machines starting with blank tapes built from Turing machines with known tape
inputs.  This correspondence arises because an equivalent Turing machine
starting with no input on its tape can always be constructed from a Turing
machine with KNOWN input by adding initial states that reconstruct the tape
contents 'from scratch'.  This process of converting an arbitrary Turing
machine and its input to the encoding of an equivalent no-input Turing machine
REQUIRES that the input be given.

Suppose the encoding scheme is not Turing's but instead this scheme of
`no-input conversion,' for which (b) holds.  Then the encoding of T(x),
instead of a function of the states in T as `T?' before, it is a function of
the states AND the corresponding input: ?(T,x).  Turing's proof applies iff
?(T,x) = t for all x for some t.  But this is clearly NOT the case for
no-input conversion encoding.

This encoding scheme suggests defining a new class of machines.  Every Turing
machine has an infinite number of no-input Turing machines associated with
it under the conversion.  These collectively define a `computation' just as a
single Turing machine does.  I define this set as the ``particle machines''
{M1,M2,M3} associated with the ``wave machine'' M, M = {M1,M2,M3}.  When the
input is KNOWN the wave-machine collapses into a particular particle-machine.
Note that particle-machines are a subset of the set of all (or no-input)
Turing machines, and (some?) no-input Turing machines are elements of
wave-machines.  A wave-machine can be simulated by a Turing machine IFF its
input is GIVEN.

Is it the case that wave-machines are equivalent in computational power to
Turing machines?  If this were the case, any proof that applied to a Turing
machine would be equally applicable to a wave-machine.  However, as stated, 
Turing's proof for the undecidability of the halting problem is rendered 
inapplicable in the new domain (modelled by the introduction of the new axiom).
This implication has significant ramifications for Turing's thesis and
future discoveries.  Can H(x,y) be computed by a wave-machine?

- - -

I encourage researchers to take up the search for variations of the halting
algorithm, and to view Turing's result only as the first, not final, word on
problem solving capability in an extremely subtle theoretical
field, requiring investigations conducted with the utmost delicacy.
The history of mathematical thought is strewn with astonishing
surprises and computer science is far from filling its quota!



--

ld231782@longs.LANCE.ColoState.EDU