Terminating Turmite: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
→Values: updated TT(4) and TT(2,4) champions |
||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
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 '''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. | ||
== History == | == History == | ||
2D [[wikipedia:Turmite|Turmites]] also called '''turNing machines''' have been historically studied by Chris Langton in 1986 ([[wikipedia:Langton's_ant|Langton's ants]]), Allen Brady in 1988 (TurNing machines) and Greg Turk in 1989 (tur-mites). Until recently, it seems like much less investigation was put into 1D Turmites. | 2D [[wikipedia:Turmite|Turmites]], also called '''turNing machines''', have been historically studied by Chris Langton in 1986 ([[wikipedia:Langton's_ant|Langton's ants]]), Allen Brady in 1988 (TurNing machines) and Greg Turk in 1989 (tur-mites). Until recently, it seems like much less investigation was put into 1D Turmites. | ||
==Values== | ==Values== | ||
{| class="wikitable" | |||
!Domain | |||
!Value | |||
!Champion | |||
|- | |||
|TT(2) | |||
|≥ 13 | |||
|<code>1TB---_1PA0PB</code> | |||
|- | |||
|TT(3) | |||
|≥ 82 | |||
|<code>1PB0PA_1TA0PC_1PA---</code> | |||
|- | |||
|TT(4) | |||
|≥ 48,186 | |||
|<code>1TB1PA_1PC0PA_1TA0PD_---1TA</code> | |||
|- | |||
|TT(2,3) | |||
|≥ 223 | |||
|<code>1TB0PA2PA_2PA---1PA</code> | |||
|- | |||
|TT(3,3) | |||
|≥ 45,153 | |||
|<code>1PB1PA1TA_2TB2PB2PC_---2PA1TC</code> | |||
|- | |||
|TT(2,4) | |||
|> 3.467*10<sup>15</sup> | |||
|<code>1TA2PB3TB---_3TA1PB1TA1PA</code> | |||
|} | |||
== See Also == | == See Also == | ||
* Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0 | * Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0 | ||
[[category:Functions]] | [[category:Functions]] | ||
Latest revision as of 22:28, 9 January 2026
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.
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). Until recently, it seems like much less investigation was put into 1D Turmites.
Values
| Domain | Value | Champion |
|---|---|---|
| TT(2) | ≥ 13 | 1TB---_1PA0PB
|
| TT(3) | ≥ 82 | 1PB0PA_1TA0PC_1PA---
|
| TT(4) | ≥ 48,186 | 1TB1PA_1PC0PA_1TA0PD_---1TA
|
| TT(2,3) | ≥ 223 | 1TB0PA2PA_2PA---1PA
|
| TT(3,3) | ≥ 45,153 | 1PB1PA1TA_2TB2PB2PC_---2PA1TC
|
| TT(2,4) | > 3.467*1015 | 1TA2PB3TB---_3TA1PB1TA1PA
|
See Also
- Google Sheet recording known values: https://docs.google.com/spreadsheets/d/18EXcLXM4Xb_qpKenV4oRGQQpCd45MJ4uawNWgmVvKTY/edit?gid=0#gid=0