Simple binary Turing machines, their numbering, behaviour and output.

1. Wolfram’s numbering scheme of Turing machines with s states and k characters, half infinite tape and no explicit halting state.

Number of Turing machines with s states and k characters (binary machines are enligthed) :

s→2 | s→3 | s→4 | s→5 | |

k→2 | 4096 | 2985984 | 4294967296 | 10240000000000 |

k→3 | 2985984 | 198359290368 | 36520347436056576 | 14348907000000000000000 |

k→4 | 4294967296 | 36520347436056576 | 1208925819614629174706176 | 109951162777600000000000000000000 |

k→5 | 10240000000000 | 14348907000000000000000 | 109951162777600000000000000000000 | 2980232238769531250000000000000000000000000 |

Instructions table of a machine whose rule number is given (instructions refers to Wolfram’s original mode but shiftedinstructions should have been more judicious) :

Rule number of a machine whose instructions table is given :

Clearly TMNumber annihilates instructions :

The s×k triplets, (s,k,d), associated to a given rule, in Wolfram’s canonical order (s =1, 2, ...; k=0, 1, ...; d=-1,+1) :

The same triplets in shifted mode (s =0, 1, ...; k=0, 1, ...; d=0,1) :

Recovering the machine rule number from the shifted triplets :

Analysis of the 4096 2-states binary machines.

Activation of preliminary instructions :

Search for the first time a new sequence is printed :

Summary when s=2 (Symmetric sequences have been set as equals) :

Analysis of the 2985984 3-states binary machines.

Activation of preliminary instructions :

Search for new sequences :

Analysis of the 4294967296 4-states binary machines (Incomplete).

Activation of preliminary instructions :

Search for new sequences :

2. Modified numbering scheme of Turing machines with s states and k characters, half infinite tape and no explicit halting state.

Once s and k are known, their exist 2s k distinct triplets (numbered from 0 to 2s k - 1) :

Running a particular machine (new numbering !) :

Even on a multi core PC Mathematica is unable to run 4294967296 machines in a reasonable time (a few days are needed). A C++ program is much more rapid and GPU programming helps a lot : a few minutes suffice !

Treatment of the sequences output by 4-states binary TM (Parallelized in C++ : MT4_cuda.exe -> MT4.txt).

Reading the output file in Mathematica ({Machine number, number of steps, printed sequence}) :

Busiest beaver :

Most productive beaver :

{Machine number, logical depth, printed sequence} :

Symmetrization and reordering of the results (sequence, reversed sequence, conjugate sequence and reversed conjugate sequence) :