Registered: Mar 2010
The 2D Turing machine on page 186 is actually periodic
The 4-state 2-color 2D Turing machine on page 186 of NKS is described as "one example where the behavior seems in many respects completely random."
In fact the pattern is periodic. To verify this, load Golly and run this script, supplying the specification string for this Turing machine:
The attached image shows the state after around 5 million timesteps. Two marks 'a' and 'b' indicate matching points. The period is 2,074,575.
It's not terribly significant of course but worth noting.
Perhaps more significant is that, contrary to the implication on p. 184, there are 3-state 2-color 2D Turing machines that exhibit complex behaviour. E.g.:
Seemingly random for 15.5 million timesteps, before making a repetitive highway.
Grows phenomenally slowly, presumably through some form of counting but it isn't obvious how and the pattern appears random.
tim_hutton has attached this image:
Report this post to a moderator | IP: Logged