Single-state multiple-head Turing machines

We can create Turing machines with no internal states if we have multiple heads.

The question is how many colours do we need?

Assuming the 3 state, 2 colour Turing machine is the simplest.

For 1 head: Not Possible with 1 state
For 2 heads: <=6 colours
For 3 heads: <=6 colours (4?)
....


For 2 colours: >=2 heads
...
For 6 colours: 2 heads

For example this is Universal:

0101001001001[010]00101010

0101010001010[110]11010100

0101110000000[111]10101010

But is this? (4 colours, 2 heads)?

CTAGAGCATGC[CGT]CGACTCAG

Or equivalently this?

100101110[10]10101010

001011100[11]10100101

Restricing the idea so that the ends must be repeated symbols. Then the (6,4) is the simplest which corresponds to 2 heads with 24 colours. So at least

ABCHSADBJSADHSA[CX]ADBSADBSAHJDS

Can be made Universal using only 24 letters of the alphabet.

Using the more tighter idea of a Turing machine without repeating patterns at the ends. Using (2,4) Turing machine then 8 colours with 2 heads suffice. Which still allows the 3 rows of binary numbers.

Paul's Ant

It would be interesting to generate random rules with directions of movements for this:

100101110[10]10101010

001011100[11]10100101

Either with random noise or blank screen to start. With a maximum of three digits one of the set of rules is the Universal Turing machine! Perhaps try in Canvas with HTML5.

Question, can DNA be used as a Turing complete machine just looking at 3 letters at a time? (This might be equivalent to 2 heads with sqrt(4x4x4) colors = 8 colors?? Seems like it could work!


Therefor perhaps any program can be written into DNA with a single reader, reading 3 characters at a time, and able to change the letters. What is this universal computer? It would have rules like this:

CAG ==> TGA   (move left)
CCT  ==> GGC  (move right)
GAA ==> CCT   (move left)

64 rules