Non-halting Turing machine: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
== Classification == | == Classification == | ||
* Cyclers | * Cyclers | ||
* Translated cyclers | * Translated cyclers | ||
* Bouncers | * Bouncers (first seen in 2x2) | ||
* Bells | * Bells | ||
** Exponential bells (first seen<ref>By "first seen" I mean either minimal in number of states '''or''' minimal in number of symbols</ref> in 3x2) | ** Exponential bells (first seen<ref>By "first seen" I mean either minimal in number of states '''or''' minimal in number of symbols</ref> in 3x2) | ||
| Line 11: | Line 10: | ||
** Quartic bells (first seen in 5x2) | ** Quartic bells (first seen in 5x2) | ||
** etc... | ** etc... | ||
* Counters | ** Irregular bells | ||
* Counters (first seen in 2x2) | |||
** Regular | ** Regular | ||
** Irregular | ** Irregular | ||
| Line 21: | Line 21: | ||
* Spaghetti | * Spaghetti | ||
* Cellular automata (first seen in 5x2 and 3x3) | * Cellular automata (first seen in 5x2 and 3x3) | ||
Sometimes phase transitions can occur. For example, {{TM|1RB1RC_1LC0RA_0LB0LD_1LA1LD}} starts out as an irregular bell but phase transitions into a translated cycler with period 4222 at step 29754825. | |||
== Records == | |||
=== Translated cycler preperiod === | |||
* 3x2: 101 (proven): {{TM|1RB1LB_0RC0LA_1LC0LA}} (period = 24) | |||
* 4x2: 119,120,230,102 (current champion): {{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}} (period = 966,716) | |||
* 2x4: 293,225,660,896 (current champion): {{TM|1RB2LA0RA3LA_1LA1LB3RB1RA}} (period = 483,328) | |||
=== Translated cycler period === | |||
* 3x2: 92 (proven): {{TM|1RB0LA_0RC1LA_1LC0RB}} (preperiod = 0) | |||
* 4x2: 212,081,736 (current champion): {{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}} (preperiod = 5,248,647,886) | |||
* 2x4: 33,209,131 (current champion): {{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}} (preperiod = 63,141,841) | |||
By the uncomputability of the Busy Beaver function, it is reasonable to believe that there can never be a complete classification of behaviors of Turing machines for arbitrarily high numbers of states. | By the uncomputability of the Busy Beaver function, it is reasonable to believe that there can never be a complete classification of behaviors of Turing machines for arbitrarily high numbers of states. | ||
Revision as of 23:05, 3 November 2024
(Very rough sketches and outlines)
Classification
- Cyclers
- Translated cyclers
- Bouncers (first seen in 2x2)
- Bells
- Exponential bells (first seen[1] in 3x2)
- Cubic bells (first seen in 3x2)
- Quartic bells (first seen in 5x2)
- etc...
- Irregular bells
- Counters (first seen in 2x2)
- Regular
- Irregular
- Exponential/tetration...
- Hybrid (counter-counter, bouncer-counter)
- Fractals
- Cube-like fractals (first seen in 4x2)
- Christmas tree fractals (first seen in 2x4)
- Spaghetti
- Cellular automata (first seen in 5x2 and 3x3)
Sometimes phase transitions can occur. For example, 1RB1RC_1LC0RA_0LB0LD_1LA1LD (bbch) starts out as an irregular bell but phase transitions into a translated cycler with period 4222 at step 29754825.
Records
Translated cycler preperiod
- 3x2: 101 (proven):
1RB1LB_0RC0LA_1LC0LA(bbch) (period = 24) - 4x2: 119,120,230,102 (current champion):
1RB1LC_0LA1RD_0RB0LC_1LA0RD(bbch) (period = 966,716) - 2x4: 293,225,660,896 (current champion):
1RB2LA0RA3LA_1LA1LB3RB1RA(bbch) (period = 483,328)
Translated cycler period
- 3x2: 92 (proven):
1RB0LA_0RC1LA_1LC0RB(bbch) (preperiod = 0) - 4x2: 212,081,736 (current champion):
1RB0LA_0RC1RD_1LD0RB_1LA1RB(bbch) (preperiod = 5,248,647,886) - 2x4: 33,209,131 (current champion):
1RB0RA3LB1RB_2LA0LB1RA2RB(bbch) (preperiod = 63,141,841)
By the uncomputability of the Busy Beaver function, it is reasonable to believe that there can never be a complete classification of behaviors of Turing machines for arbitrarily high numbers of states.
- ↑ By "first seen" I mean either minimal in number of states or minimal in number of symbols