Non-halting Turing machine: Difference between revisions
Jump to navigation
Jump to search
(Created page with "(Very rough sketches and outlines) == Classification == * Cyclers * Translated cyclers * Bouncers * Bells ** Exponential bells ** Cubic bells ** Quartic bells ** etc... * Counters ** Regular ** Irregular ** Exponential/tetration... * Hybrid (counter-counter, bouncer-counter) * Fractals ** Cube-like fractals ** Christmas tree fractals * Spaghetti * Cellular automata By the uncomputability of the Busy Beaver function, it is reasonable to believe that there can never be...") |
No edit summary |
||
| Line 7: | Line 7: | ||
* Bouncers | * Bouncers | ||
* Bells | * Bells | ||
** Exponential 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) | ||
** Cubic bells | ** Cubic bells (first seen in 3x2) | ||
** Quartic bells | ** Quartic bells (first seen in 5x2) | ||
** etc... | ** etc... | ||
* Counters | * Counters | ||
| Line 17: | Line 17: | ||
* Hybrid (counter-counter, bouncer-counter) | * Hybrid (counter-counter, bouncer-counter) | ||
* Fractals | * Fractals | ||
** Cube-like fractals | ** Cube-like fractals (first seen in 4x2) | ||
** Christmas tree fractals | ** Christmas tree fractals (first seen in 2x4) | ||
* Spaghetti | * Spaghetti | ||
* Cellular automata | * Cellular automata | ||
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 22:57, 3 November 2024
(Very rough sketches and outlines)
Classification
- Cyclers
- Translated cyclers
- Bouncers
- Bells
- Exponential bells (first seen[1] in 3x2)
- Cubic bells (first seen in 3x2)
- Quartic bells (first seen in 5x2)
- etc...
- Counters
- 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
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