Main Page: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
| 2-symbol || [[BB(2)]] = 6 || [[BB(3)]] = 21 || [[BB(4)]] = 107 || [[BB(5)]] = 47,176,870 || [[BB(6)]] > <math>10 \uparrow \uparrow 15</math> | | 2-symbol || [[BB(2)]] = 6 || [[BB(3)]] = 21 || [[BB(4)]] = 107 || [[BB(5)]] = 47,176,870 || [[BB(6)]] > <math>10 \uparrow \uparrow 15</math> | ||
|- | |- | ||
| 3-symbol || [[BB(2,3)]] = 38 || [[BB(3,3)]] > 10^17 || [[BB(4,3)]] > 10^14072 || || | | 3-symbol || [[BB(2,3)]] = 38 || [[BB(3,3)]] > <math>10^{17}</math>|| [[BB(4,3)]] > <math>10^{14072}</math>|| || | ||
|- | |- | ||
| 4-symbol || [[BB(2,4)]] = 3,932,964 || [[BB(3,4)]] > 2(^<sup>15</sup>)5 + 14 || || || | | 4-symbol || [[BB(2,4)]] = 3,932,964 || [[BB(3,4)]] > 2(^<sup>15</sup>)5 + 14 || || || | ||
|- | |- | ||
| 5-symbol || [[BB(2,5)]] > 6.5 × 10^38033 || || || || | | 5-symbol || [[BB(2,5)]] > 6.5 × <math>10^{38033}</math>|| || || || | ||
|} | |} | ||
Revision as of 09:30, 8 June 2024
The Busy Beaver function BB (called S originally) was introduced by Tibor Radó in 1962 [1] for 2-symbol Turing machines and later generalised[2] to m-symbol Turing machines:
| BB(n,m) = Maximum number of steps done by a halting m-symbol Turing machine with n states starting from all-0 memory tape |
The busy beaver function is not computable and, few of its values are known:
| 2-state | 3-state | 4-state | 5-state | 6-state | |
| 2-symbol | BB(2) = 6 | BB(3) = 21 | BB(4) = 107 | BB(5) = 47,176,870 | BB(6) > |
| 3-symbol | BB(2,3) = 38 | BB(3,3) > | BB(4,3) > | ||
| 4-symbol | BB(2,4) = 3,932,964 | BB(3,4) > 2(^15)5 + 14 | |||
| 5-symbol | BB(2,5) > 6.5 × |
Notes
- ↑ Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x
- ↑ Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.