|
Zoomer Antimillenarian@surcomplicated.bsky.social |
There are definitely some meaningful problems that can be expressed in terms of 5-state Turing machines, because they managed to find a few in the vast zoo of those machines.
1 replies 0 reposts 1 likes
|
|
Zoomer Antimillenarian
@surcomplicated.bsky.social
[ View ] |
Again, not very many, but we now have a neat trick to solve any problem that can be decomposed into questions about the halting or nonhalting of 5-state (one-zeroed-out-tape, 2-symbol) Turing machines.
1 replies 0 reposts 1 likes