Non-halting Turing machine: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 20: | Line 20: | ||
** Christmas tree fractals (first seen in 2x4) | ** Christmas tree fractals (first seen in 2x4) | ||
* Spaghetti | * Spaghetti | ||
* Cellular automata | * Cellular automata (first seen in 5x2 and 3x3) | ||
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 (first seen in 5x2 and 3x3)
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