Registered: Mar 2010
Posts: 4

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:

code:
{{{1,'N',1},{0,'S',1}},{{1,'S',3},{0,'N',2}},{{1,'W',0},{1,'N',1}},{{1,'S',2},{0,'E',1}}}

code:
{{{0,'S',1},{1,'W',1}},{{1,'E',2},{1,'S',2}},{{1,'W',0},{0,'N',0}}}

code:
{{{0,'N',2},{1,'S',1}},{{0,'E',0},{0,'S',0}},{{1,'W',1},{1,'N',2}}}

tim_hutton has attached this image:

Report this post to a moderator | IP: Logged

Registered: Dec 2003
Posts: 21

I'm curious. How did you find this periodic relationship millions of steps into the process?

Report this post to a moderator | IP: Logged

Registered: Mar 2010
Posts: 4

Hi Michael,

Visual inspection. You can see it for yourself in the image - the bumps at 'a' and 'b' look the same. After that it's easy to confirm.

For patterns that aren't so visually cooperative (perhaps they make too straight a line when zoomed out) there are other ways of achieving the same thing: take some measure on each row/column for example, and plot this measure. Then patterns that repeat are easy to spot (for small enough iteration counts).

I've put some more results and an explanation of the notation here (http://code.google.com/p/ruletablerepository/wiki/TwoDimensionalTuringMachines).

The search for Busy Beavers in these 2D Turing machines is quite interesting.

Tim

Report this post to a moderator | IP: Logged

Registered: Dec 2003
Posts: 21

I can see this repeating pattern perfectly. Let me ask my question differently.

Suppose you have a rule you look at - 1000 iterations and you see repetition.

Another rule - 1000 iterations and no repetition. Is it non-repeating?

You check 1,000,000 iterations. Nothing.

10,000,000?

Is there a way to know?

Thanks - and I'll take a look at your site.

Report this post to a moderator | IP: Logged

Registered: Mar 2010
Posts: 4

Sorry to misunderstand your question.

There's no general algorithm - this is the halting problem.

Report this post to a moderator | IP: Logged

Registered: Mar 2010
Posts: 4

Here's an animation of the slow-growing 3-state 2-color 2D Turing machine I mentioned, from 1 billion up to 100 billion timesteps.

Adam Goucher suggested that some of the time it is counting in base-phi, which I struggle to understand!

http://mathworld.wolfram.com/Base.html

tim_hutton has attached this image:

Report this post to a moderator | IP: Logged

Registered: Not Yet
Posts: N/A

Originally posted by tim_hutton
Hi Michael,

Visual inspection. You can see it for yourself in the image - the bumps at 'a' and 'b' look the same. After that it's easy to confirm.

For patterns that aren't so visually cooperative (perhaps they make too straight a line when zoomed out) there are other ways of achieving the same thing: take some measure on each row/column for example, and plot this measure. Then patterns that repeat are easy to spot (for small enough iteration counts).

I've put some more results and an explanation of the notation here (http://code.google.com/p/ruletabler...lTuringMachines).

The search for Busy Beavers in these 2D Turing machines is quite interesting.

Tim

Report this post to a moderator | IP: Logged