4 ms·
Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...
by snaily 9y ago
Have you seen how quickly busy beaver functions grow with the size of the program? It'd have to be a pretty restricted system to be tractable...
- userbinator 9y agoThose are still predicated on having an infinite tape. With finite storage, every program becomes a finite-state machine; and to "solve" the halting problem, one only needs to use the usual cycle-finding algorithms.
- adrianN 9y agoWith more than a handful of bits of state ever this restricted form of the halting problem is not solvable in general in practice. It's like saying "reading AES encrypted stuff is easy, you just have to try all keys"
- madez 9y agoWhat is the relation between busy beavers on turing machines and cycle finding in finite state machines?