[FOM] 2,3 Turing machine proof controversy

[Clive Gifford]

Alex Galicki wrote:
> 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.

I have also asked Alex Smith (yesterday, in an email direct to him) if he
can elaborate on this. Like you I couldn't find a description in the proof
of how we are to recognise that the cyclic tag system being emulated has
terminated. It may be there but just hard to find!

One part of Alex's proof that hasn't caused any controversy (that I'm aware
of), is his claim to be able to construct a finite initial condition that
will emulate a target cyclic tag system for an arbitrary (but still finite)
number of cycles. I have been thinking about this, as it strongly suggests
to me that universality with a finite non-blank initial configuration might
be "quite close". And obviously we need to be able to recognise if an
emulation for, let's say, a googol of cycles actually terminates somewhere
before the end of that full sequence. We can also put some even bigger
numbers in there, instead of "googol" if we wish, perhaps a googolplex of
cycles sounds better?

All this thinking about very extremely large numbers, reminded me of an
article by Scott Aaronson, talking about an amusing idea for a competition
amongst a group of people in a room, where a challenge is issued to write
down a number larger than that written by any other person in the room in
less than, say, 15 seconds, and also using a notation that any reasonably
competent mathematician could understand. Here's the link:
http://www.scottaaronson.com/writings/bignumbers.html
Eventually he ends up talking about the Busy Beaver numbers, and this gave
me an idea.

Start by formulating a version of the Busy Beaver problem for the particular
cyclic tag system that we want to emulate via Alex Smith's construction
method (the one that always produces a finite initial condition), where the
Busy Beaver value in this case is the maximum number of cycles that can be
executed by that particular "size" of cyclic tag system before it must
definitely terminate -- if it ever is going to terminate. (I'm assuming
there is an appropriate rule to recognise if the emulated cyclic tag system
terminates.) By definition, if it hasn't terminated after that many cycles
then we know it never will.

This Busy Beaver value exists, even though we don't know what it is.
Therefore, there exists a finite initial condition, constructible using Alex
Smith's method, that will allow us to emulate the cyclic tag system for up
to that many cycles (and if it terminates before that number of cycles has
been run then we can recognise this and decode the result). In other words,
there exists a finite initial configuration that will be large enough to
complete the emulation for any cyclic tag system, but we can never hope to
know exactly what it is.

So, assuming a suitable halting rule, and that the finite construction
method in Alex's proof is correct, this says to me that this machine is in
fact universal and also with a finite "non-blank" initial tape
configuration, but unfortunately one that we cannot actually produce as
evidence.

On the other hand, if we cannot accept universality when the initial tape
configuration can't actually be explicitly known (even though it is finite
and does exist "out there" somewhere), then perhaps this tells us nothing.

So, is the 2,3 prize machine universal with infinite non-repetitive initial
tape, or universal with a finite "non-blank" initial configuration that is
simultaneously beyond our reach, or is this still an open question? Don't
forget, somewhere out to the right of the infinite tape configuration
constructed in Alex's full proof, we're potentially going to be running the
emulation for any number of cycles greater than the Busy Beaver value
described above...

You have 15 seconds to answer, but please note that I also freely admit to
not being a very competent mathematician!

Clive Gifford