Terminating Turmite
A Terminating Turmite or Relative Movement Turing Machine is a 1 dimentional Turing machine which uses relative directions instead of absolute ones. So instead of moving (L)eft or (R)ight, it (P)roceeds forward (for one step in the same direction as last move) or (T)urns-around (move one direction in the opposite direction). TT(n,k) is the maximum steps of all halting n-state, k-symbol Terminating Turmites when started on a blank tape.
A multidimensional Terminating Turmite is a Terminating Turmite that use a multidimensional tape instead. These Terminating Turmites have (2*dimension count) different moving directions, 2 each for 1 dimension. Example: 1RB0TA_1PA0LB is a 2-dimensional Terminating Turmite, used P, T, L (Turn Left), R (Turn Right) 4 moving directions. TT_2D(n,k) is the maximum steps of all halting n-state, k-symbol 2D Terminating Turmites when started on a blank tape.
History
2D Turmites, also called turNing machines, have been historically studied by Chris Langton in 1986 (Langton's ants), Allen Brady in 1988 (TurNing machines), and Greg Turk in 1989 (tur-mites). A collaborative effort led by Tim Hutton since 2011 has considered turmites on 2D square, triangular, and hexagonal grids. Until recently, it seems like much less investigation was put into 1D Turmites.
Values
| Domain | Runtime | Champion |
|---|---|---|
| TT(n,1) and TT_2D(n,1) | n | Trivial |
| TT(1) | 3 | 1TA1PZ
|
| TT(2) | ≥ 13 | 1TB---_1PA0PB
|
| TT(3) | ≥ 82 | 1PB0PA_1TA0PC_1PA---
|
| TT(4) | ≥ 48,186 | 1TB1PA_1PC0PA_1TA0PD_---1TA
|
| TT(1,3) | ≥ 5 | 1TA2PA1PZ
|
| TT(2,3) | ≥ 223 | 1TB0PA2PA_2PA---1PA
|
| TT(3,3) | > | 1PB0TC1PA_2PC1PZ2PA_2TC0PA2PC
|
| TT(1,4) | ≥ 9 | 1TA2PA3PA1PZ
|
| TT(2,4) | > 3.467*1015 | 1TA2PB3TB---_3TA1PB1TA1PA
|
| TT2D(1) | 5 | 1RA1PZ
|
| TT2D(2) | ≥ 121 | 1LA0LB_1PZ1RA
|
| TT2D(3) | ≥ 21,790 | 1RB1PA_1RB1RC_1PZ1PA
|
| TT2D(4) | ≥ 287,251 | 1PB0TD_0RA0PC_1PZ0TB_1PA0PA
|
| TT2D(1,3) | ≥ 9 | 1RA2RA1PZ
|
| TT2D(2,3) | ≥ 59,348,218 | 1RB2TB2PZ_1RA1PB1TB
|
| Domain | Score | Champion |
|---|---|---|
| TT(3,3) | ≥ 32,778 | 1PB2PA0PC_2TB1PC2PB_2PB1PZ0PA
|
See Also
- Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0