[Universal Computation with only 6 States] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Universal Computation with only 6 States

(Click here to view the original thread with full colors/images)


Posted by: Alastair Hewitt

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


Posted by: Craig Feinstein

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?


Posted by: Alastair Hewitt

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.


Posted by: Craig Feinstein

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!


Posted by: Craig Feinstein

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!




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings