[FOM] 2,3 Turing machine proof controversy

[Alexander Smith]

(This message is addressed directly at Vaughan Pratt, but CC'd to FOM because other people there may find it of interest.) 
 
I've been thinking through the arguments made about my proof (the problem being a discussion of exactly what it is that it does prove, whether universality or something weaker), and I'd like to be clear on exactly what your objection to it is; I think I understand, but it's important to be very clear on the details. The following argument is an attempted rebuttal to the objection; I'd be interested if you tell me exactly where it breaks down, because then I'll understand what some of the deficiencies are in my understanding of your objection or of  this area of mathematics.
 
Consider some hypothetical Turing machines that take an input tape consisting of a cyclic tag system translated into an input tape in a specific simple way (explained below). I'll give them five possible colours for each tape element: 0, 1, _, X, and R.
 
The first hypothetical Turing machine takes a tape like this:
 
..._________R0110_01_110_________________________________...
 
This Turing machine, when starting at the R on this tape, emulates the cyclic tag system starting with initial string 0110 and with rules 01 and 110 for two steps: one for each rule. (So it's a bit degenerate in the sense that it doesn't cycle the rules; it stops after the last one.) Presumably, we both agree that if such a machine could only accept finite input, it wouldn't be universal. (It's pretty trivial to create an LBA that can process such input (minus the infinite leading and trailing blank part of the tape) and emulate the cyclic tag system, for instance. It could even be given a halt state to prevent the problem with what 'emulate' means.) It's possible to imagine running the Turing machine on that input, and then on the input for three steps, and then on the input for four steps, and so on, but that doesn't show universality because the Turing machine has to be restarted by hand each time.
 
Now imagine what happens if I give the same Turing machine input like this:
 
..._________R0110_01_110_01_110_01_110_01_110_01_110_01_110_...
 
This infinite input will cause the cyclic tag system to be emulated forever, which if the initial condition is accepted to be acceptable is a proof of universality. This is a simple periodic initial condition, created by looping the rules of the cyclic tag system forever; such initial conditions are used, for instance, for the rule 110 universality proof. I would contend that this Turing machine is, therefore, universal. However, above it's already been seen that an LBA can do the same thing on the same sort of input. Does this mean that an LBA is universal? I'd contend no: an infinite amount of input simply can't be given to an LBA, because then it would trivially be universal, and so this implies that the definition of an LBA must exclude the possibility of an infinite input. (I haven't seen the famous proof that LBAs cannot be universal, but suspect that one of the assumptions or definitions it makes is that LBAs only accept a finite amount of input, because without that assumption it seems pretty easy to prove that LBAs are universal because when given an infinite amount of input they are equivalent to Turing machines; please let me know if I'm wrong about this.)
 
Now suppose the Turing machine in question needs some 'thinking space': that is, some Xs need to be placed on the tape next to every rule for it to work the same way as before, so that it takes input like this:
 
..._________R0110_01XX_110XX______________________________...
 
This Turing machine is not guaranteed to work unless there are at least as many Xs next to each rule as the number of rules in the emulation. This can also be easily implemented by an LBA for finite input - after all, it would be possible to use the same LBA as in the first part but set up to skip Xs - but the infinite repeating input shown before does not work. However, once the system finishes simulating a cyclic tag system, it can go on and do another written later on the tape:
 
..._________R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_____...
 
This input would tell that Turing machine to emulate the cyclic tag system starting at 0110 with rules 01 and 110 first for 2 steps, then for 3 steps. Again, it's easy to come up with an LBA that emulates this for finite input.
 
Can this system be universal? Imagine the following input:
 
...__R0110_01X_R0110_01XX_110XX_R0110_01XXX_110XXX_01XXX_R...
 
This input tells the system to emulate the cyclic tag system for one step, then two steps, then three steps, then so on. The input to this system isn't periodic, but is simple to construct in a non-universal way. Is this Turing machine universal? With the definition I used in the 2,3 Turing machine universality proof, yes. Does this definition show that an LBA is universal? No, because there is one infinite input here, and an LBA can't be given an infinite amount of input. It's possible to imagine the LBA running on the input for one step, then the input for two step, then the input for three steps, and so on, but that requires restarting by hand; this argument illustrates that restarting by hand should not be allowed in a universality definition precisely because it does allow LBAs to be universal.
 
The 2,3 Turing machine universality proof uses an initial condition similar to the last one here; a representation of the cyclic tag system to one step, followed by a representation to two steps, followed by a representation to three steps, and so on, with extra padding added each time. (Actually, the representation would be to two, four, and six in this case, or in general steps where the set of rules is repeated an integral number of times, to make constructing the initial condition easier, but that's just a detail and doesn't affect this argument.) The construction for the initial condition is slightly more complicated, because the rules have to be encoded in a more complicated manner and the Xs that govern how many rules can be used aren't just put in the well-behaved location just after each rule but instead spread over the whole representation in a complicated manner, and they increase faster than just linearly, but the point is that the input is simple and obviously not doing any universal calculation itself, so the Turing machine as a whole is universal. Again, this definition doesn't show that an LBA is universal, because an LBA can't take an infinite amount of input unless it's run an infinite number of times, and the definition only allows for running an LBA once.
 
I'd be interested to know where the argument I've given above conflicts with your understanding of my proof or my definition of universality, with my understanding of your rebuttal, or with my understanding of mathematics; that way, the current situation should become a bit clearer.
 
-- 
Alex Smith