Advanced topics on Busy Beavers

Contents

Tables normalization

Page in progress

Tables normalization

A permutation of states, or a permutation of symbols, does not change the behavior of a Turing machine.
Suppose you get two Turing machines, taking the same time to stop on an initially blank tape. How to know whether these machines are essentially different, or they are just the same machine up to a permutation of states or symbols?
To settle this problem, you can normalize the table, putting it in tree normal form (TNF).

Since we are interested by the behaviors of Turing machines on an initially blank tape, the simplest rule is the following one:

When the Turing machine is launched on a blank tape:
So, normally, the first transition is A0 --> 1RB.

As an example, we give below the tables of the Turing machines as found by Terry and Shawn Ligocki, and their normalized version as given in the present web pages.

Turing machines with 2 states and 4 symbols

A0 A1 A2 A3 B0 B1 B2 B3 sigma(M) s(M)
3RB 3RA 3RA 1LA 3LB 2RB 2LH 3LA 2,050 3,932,964
TNF: 1RB 2LA 1RA 1RA 1LB 1LA 3RB 1RH 2,050 3,932,964

Turing machines with 2 states and 5 symbols

A0 A1 A2 A3 A4 B0 B1 B2 B3 B4 sigma(M) s(M)
1RB 4LA 1LA 2LA 1RA 3LA 1RH 1RA 2RA 4RB 11,120 148,304,214
TNF: 1RB 3LA 4LA 1RA 1LA 2LA 1RH 4RA 3RB 1RA 11,120 148,304,214
4RB 2LA 4LA 4RA 3LA 1LA 4LA 4RA 3RB 3LH 3,685 16,268,767
TNF: 1RB 3LA 4LA 1RA 1LA 2LA 1RH 1LA 3RB 1RA 3,685 16,268,767
4LB 1RH 2RA 0LB 3LB 2RA 3LB 3RB 2LB 1LB 4,099 15,754,273
TNF: 1RB 3RB 2LA 0RB 1RH 2LA 4RB 3LB 2RB 3RB 4,099 15,754,273

Turing machines with 2 states and 6 symbols

A0 A1 A2 A3 A4 A5 B0 B1 B2 B3 B4 B5 sigma(M) s(M)
1RB 4LA 1RA 5LB 1RA 3LB 1LB 1LA 5LA 2LA 2RB 1RH 15,828 493,600,387
TNF: 1RB 2LA 1RA 1RA 5LB 4LB 1LB 1LA 3RB 4LA 1RH 3LA 15,828 493,600,387
4RB 4RA 4RA 1LA 1LA 1LB 4LB 2RB 5LB 3RA 3LA 1RH 10,249 98,364,599
TNF: 1RB 3LA 3LA 1RA 1RA 3LB 1LB 2LA 2RA 4RB 5LB 1RH 10,249 98,364,599
5RB 5RA 3RH 1RB 3LA 1LA 4LB 1RB 4LH 2RA 5LB 5LA 10,574 94,842,383
TNF: 1RB 3LA 4LA 1RA 3RB 1RH 2LB 1LA 1LB 3RB 5RA 1RH 10,574 94,842,383

Turing machines with 3 states and 4 symbols

A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 sigma(M) s(M)
1RB 2LC 0LC 0RA 3LC 2RC 1LB 0RC 1RA 0LB 1RH 0RB 17,323 262,759,288
TNF: 1RB 3LC 0RA 0LC 2LC 3RC 0RC 1LB 1RA 0LB 0RB 1RH 17,323 262,759,288

Turing machines with 4 states and 3 symbols

A0 A1 A2 B0 B1 B2 C0 C1 C2 D0 D1 D2 sigma(M) s(M)
0RB 1RH 2LD 2LA 2RD 2RC 2RB 2RC 1LC 2LA 1RB 2LC 15,008 250,096,776
TNF: 0RB 1LD 1RH 1LA 1RC 1RD 1RB 2LC 1RC 1LA 1LC 2RB 15,008 250,096,776

 

Link to the home page of Pascal Michel