[FOM] 2,3 Turing machine proof controversy
Alex Galicki
alex.galicki at googlemail.com
Sun Nov 11 21:10:18 EST 2007
On 11/11/2007, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> (My reply to Bob Hearn subsumes that to Alex. By way of background
> information on Bob he is a Clarisworks principal who has more recently
> obtained some very nice results in collaboration with Erik Demaine and
> others. Bob's ClarisWorks killed Microsoft Works in 1991, Bob's
> collaboration with Erik began a decade later.)
>
> Bob Hearn wrote:
> > My understanding is that this is in fact the way Smith's construction
> > works. There are no restarts, merely a single run from an infinite
> > initial condition. Did I misunderstand?
>
> Although I still haven't figured out just where in Alex's paper it says
> this explicitly I'll go with this interpretation. (As I understand him
> Alex is claiming that it's in the condition on page 4 of his proof,
> namely "To be precise, 'finite-length initial condition', given in this
> and future conjectures, refers to an initial condition in which only
> finitely many of the cells are relevant, and no other cells are visited
> during the evolution of that initial condition." I'm happy to defer to
> any competent judge who's been able to read into this sentence what Alex
> claims to have been his intended meaning. Personally I find this all
> very fuzzy.)
This is exactly why I keep asking (without much hope) if *anyone* on
this list is able to tell me what is the exact halting rule of the 2,3
machine.
The so called 'finite-length initial condition' is the only thing I
managed to find in the proof itself, but with just that rule the 2,3
machine will either always stop (for finite input) or never (for
infinite initial condition).
A.
More information about the FOM
mailing list