wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > The 2D Turing machine on page 186 is actually periodic
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
tim_hutton


Registered: Mar 2010
Posts: 4

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:

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}}}


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.:

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

Seemingly random for 15.5 million timesteps, before making a repetitive highway.

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

Grows phenomenally slowly, presumably through some form of counting but it isn't obvious how and the pattern appears random.

Regards,

Tim

tim_hutton has attached this image:

Report this post to a moderator | IP: Logged

Old Post 03-22-2010 03:53 PM
tim_hutton is offline Click Here to See the Profile for tim_hutton Visit tim_hutton's homepage! Edit/Delete Message Reply w/Quote
Michael Round
Rational Systems, Inc.
Overland Park, KS

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

Old Post 03-26-2010 03:40 PM
Michael Round is offline Click Here to See the Profile for Michael Round Click here to Send Michael Round a Private Message Click Here to Email Michael Round Visit Michael Round's homepage! Edit/Delete Message Reply w/Quote
tim_hutton


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

Old Post 03-26-2010 04:05 PM
tim_hutton is offline Click Here to See the Profile for tim_hutton Visit tim_hutton's homepage! Edit/Delete Message Reply w/Quote
Michael Round
Rational Systems, Inc.
Overland Park, KS

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

Old Post 03-26-2010 04:53 PM
Michael Round is offline Click Here to See the Profile for Michael Round Click here to Send Michael Round a Private Message Click Here to Email Michael Round Visit Michael Round's homepage! Edit/Delete Message Reply w/Quote
tim_hutton


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

Old Post 03-26-2010 05:07 PM
tim_hutton is offline Click Here to See the Profile for tim_hutton Visit tim_hutton's homepage! Edit/Delete Message Reply w/Quote
tim_hutton


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

Old Post 04-16-2010 10:38 AM
tim_hutton is offline Click Here to See the Profile for tim_hutton Visit tim_hutton's homepage! Edit/Delete Message Reply w/Quote
mdmd


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




Thank you so much for this useful clarification

Report this post to a moderator | IP: Logged

Old Post 06-30-2010 11:51 AM
Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives