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

Alexander Smith AIS523 at bham.ac.uk
Wed Nov 14 03:19:47 EST 2007


I wrote:
> (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.)
 
It seems that I was thinking in terms of system 3, not system 0 (the 2,3 Turing machine), when I wrote this. The halt-equivalent behaviour in the original 2,3 Turing machine is the same (a specific element in the tape is in state A while not a 0), but not all the initially nonzero elements in that repetition will do in system 0, only the leftmost, the third from the left, the fifth from the left, and so on. This doesn't materially affect anything else in the discussion, but as my previous post contained a minor factual error I think it's worth correcting.
 
-- 
Alex Smith





More information about the FOM mailing list