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