[FOM] Halting rules for the 2,3 and a 2,4 Turing machine

[Alexander Smith]

More than one person has asked me about what behaviour of the 2,3 Turing machine corresponds to halting in the cyclic tag system. I apologise for not explaining this in the proof; I hadn't actually worked it out before (I knew it must correspond to something, because all aspects of the cyclic tag system are emulated, but I hadn't worked out what). Interestingly, it's possible to design a 2,4 Turing machine with a halt rule which works the same way as the 2,3 Turing machine and also allows a simpler initial condition, which unfortunately is also of the infinite non-repetitive nested form that the 2,3 Turing machine uses and so doesn't help to solve that controversy.
 
The 2,3 Turing machine, when emulating a cyclic tag system that halts, will cause certain elements in the original tape to become active in state A when they aren't coloured with 0 (when this happens, all subsequent such elements will show the same behaviour); this situation never happens with a cyclic tag system that never halts. The 2,3 Turing machine keeps on running after this point (because it doesn't have a halt rule) and in fact the extra added large integers are a workaround to cause it to keep on running in a predictable manner. If the machine is adapted to halt at this point rather than keep running, the extra added large integers are unnecessary and so the initial condition will cause emulation at a faster rate (in terms of computational order). In order to add a halt rule, it's necessary to add extra rules, because all 6 of the current rules are used, and it's easiest to do this by adding an extra colour to make a 2,4 Turing machine, especially as the halting rule is expressed in terms of certain elements on the initial tape. (As for which elements these elements are, it's one of the elements in the 0222...220222...22022...220... sequence at the point in the initial condition that corresponds to the left-hand end of the system 4 tape; the relevant element is somewhere around the xth repetition counting from the right, where x is the minimum possible value for an extra added large integer, but I haven't worked it out rigorously and I'm worried about off-by-one errors, so all I'll say for the time being for certain is that the element in question is either in that repetition, or the repetition to its left or right, and any initially nonzero element in that repetition will do.)
 
The 2,4 Turing machine has the following rules (notation is current state and colour -> new state, new colour, movement direction):
 
A0 -> B1>
B0 -> A2<
A1 -> A2<
B1 -> B2>
A2 -> A1<
B2 -> A0>
A3 -> Halt
B3 -> B3>
 
An initial condition for this machine that causes it to emulate a cyclic tag system is produced the same way as for the 2,3 Turing machine (notice that the rules for colours 0, 1, and 2 are the same), except that there are no extra added large integers, the number of repetitions of 0222...22 in the parts of the system 3 tape that corresponds to the left hand end of each system 4 tape is limited to the minimum value that the extra large integers could have taken (from the proof for the 2,3 machine, (3^(n-1))*M+1, where M and n depend in a simple way on the original cyclic tag system and the number of steps for which it is being emulated), and a 3 is inserted after the 0 in the first repetition of 0222...22. (The values of d, e, r, w, and f can also be made smaller, but this is not necessary.) This 2,4 Turing machine helps solve the problems with recognising the halt conditions, because it has an explicit halt rule; the conditions under which it halts definitely meet all existing definitions of universality (because they are the same as for the emulated cyclic tag systems) as long as the encoding of the initial condition is accepted as being acceptable (which is the main argument that's being discussed on FOM). With the 2,4 Turing machine, and possibly even with the 2,3 Turing machine (although I'm less clear on that), I think it's possible to produce an initial condition which definitely has a nested form, by producing it with a neighbour-independent substitution system with more than 4 colours and then treating some of the colours as identical in the input to the Turing machine, but I haven't done this rigorously yet so I may be wrong on that. (It could take a while for me to do that, because I'm quite busy at the moment; that's also the reason I haven't got back to you sooner.)
 
-- 
Alex Smith