Registered: Feb 2004
Posts: 35

Following from some discussions about the threshold of computational universality, I thought I would throw this into the mix:

If we allow the rules for a Turing Machine to be bent a little and use a circular tape, then this 3 state, 2 color machine will generate rule 110 (shifted) from the standard black/white initial conditions:

{1,0} -> {1,0,1}
{1,1} -> {2,1,1}
{2,0} -> {1,1,1}
{2,1} -> {3,1,1}
{3,0} -> {1,1,1}
{3,1} -> {3,0,1}
(note the machine only moves in one direction, since the direction digit is always 1)

Obviously, to be universal it would need an infinite tape and therefore take an infinite number of steps to go around the tape, but this is no more problematic that doing universal computation on a 1D CA. In fact, to make the 1D CA "automatic" like the tape loop above, it would also have to be on a loop.

Anyway, I was not trying to claim the record for smallest Turning Machine, I wanted to point out that you can essentially do universal computation using just 6 rules. There was some speculation that 3 bits would be the limit, but it appears that rule 110 can be encoded using less than 2.6 bits (Log_2 6).

Last edited by Alastair Hewitt on 07-25-2007 at 12:06 AM

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 36

Alastair,

I don't see how the 3-state 2-color Turing machine that you presented emulates Rule 110 on a circular tape. Can you demonstrate how?

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 35

I've been doing some experiments using my own Java program. There is probably a Wolfram code number for this one, but I couldn't tell you what it is (or if the Mathematica function will allow a loop?)

Below is the constructor I use for this machine. The rules in the previous post look correct and follow the format in the NKS book:

Machine tm = new Machine( // 3 states, 2 colors
new Rule[][] { // color, state
new Rule[] {
new Rule(0, 0, Rule.Dir.RIGHT), // 0, 0
new Rule(1, 0, Rule.Dir.RIGHT), // 0, 1
new Rule(1, 0, Rule.Dir.RIGHT) // 0, 2 },
new Rule[] {
new Rule(1, 1, Rule.Dir.RIGHT), // 1, 0
new Rule(1, 2, Rule.Dir.RIGHT), // 1, 1
new Rule(0, 2, Rule.Dir.RIGHT) // 1, 2 } } );
tm.init(0, new int[]{ 1 }, 499, 0, 1000, 500);

It starts from a blank (color 0) tape of length 1000. The initial condition is the color 1 in position 500 and the head in state 0 at position 499 (it always moves to the right).

Attached is the actual output generated for 500 loops.

Alastair Hewitt has attached this image:

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 36

Alastair,

I checked this manually and it looks like indeed you have found a Turing machine which has 3-states and 2-colors on a circular tape that emulates how rule 110 would work on a circular tape. I am very surprised by this. Certainly, by any reasonable definition of universality, the machine that you have found is universal.

Congratulations! You've made an important discovery. Wolfram I'm sure would be happy about this. Your result strengthens his Principle of Computational Equivalence, which is really what I think he ultimately wanted from the 2-state 3-color machine prize problem.

Nevertheless, I don't think your example refutes my argument http://arxiv.org/abs/0706.4440 that there can be no universal Turing-machine (on an infinite-tape) having a tape-head with an information content of less than 3 bits. My argument implicitly assumes that the machine-tape is not circular.

The reason for this is because if the tape were circular, then it would not be necessary "for U to be able to determine when it is time to switch from step (1) to step (2) and from step (2) to step (1)", as I claim in my paper is the case when U has an infinite machine-tape - U would do this automatically if the machine-tape were circular, thus making it possible for the tape-head of U to have an information content of less than 3 bits.

Your machine really threw me for a loop though. Thank you!

__________________
Craig

Report this post to a moderator | IP: Logged

Registered: Nov 2004
Posts: 36

Your example has helped to convince me that my proof that there are no 2-state 3-color Turing machines is not valid. I withdrew it from the arxiv.org. I welcome anyone to try to fix my proof.

Again, congratulations on your discovery!

__________________
Craig

Report this post to a moderator | IP: Logged