Main Page: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 13: | Line 13: | ||
| || 2-state || 3-state || 4-state || 5-state || 6-state | | || 2-state || 3-state || 4-state || 5-state || 6-state | ||
|- | |- | ||
| 2-symbol | | 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)]] > <math>10^{17}</math>|| [[BB(4,3)]] > <math>10^{14072}</math>|| || | | 3-symbol || [[BB(2,3)]] = 38 | ||
| style="background: orange;" | [[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 | | 5-symbol | ||
| style="background: orange;" | [[BB(2,5)]] > 6.5 × <math>10^{38033}</math>|| || || || | |||
|} | |} | ||
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known machines in that class that believed hard to decide, such as [[Cryptids]]. | |||
==Notes== | ==Notes== | ||
<references /> | <references /> | ||
Revision as of 09:47, 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 × |
In the above table, cells are highlighted in orange when there are known machines in that class that believed hard to decide, such as Cryptids.
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.