3 ms·
The Nth Busy Beaver number lets you solve the halting problem for Turing Machines up to size N. Only a handful of them are known, for very small N, and they in
by jtolmar 3y ago
The Nth Busy Beaver number lets you solve the halting problem for Turing Machines up to size N.
Only a handful of them are known, for very small N, and they increase incredibly rapidly. For the most common version of the problem (S for 2-symbol machines), they go: 1, 6, 21, 107, some number greater than or equal to 47176870, and some number greater than 10⇈15 (that's up arrow notation on the last one).
- ijustlovemath 3y agoOoh, are they basically the number of possible turing programs encodable in a state of N?
- readams 3y agoIt's the maximum amount of time a Turing machine of size N can run. So if you want to know whether a Turning machine of size N or less will halt, just run it for BB(N) steps. If it hasn't halted by then, it never will.