Main Page: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
 
No edit summary
Line 1: Line 1:
<strong>MediaWiki has been installed.</strong>
The [[Busy Beaver function]] BB (called S originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 <ref>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</ref> for 2-symbol [[Turing machines]] and later generalised<ref>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.</ref> to m-symbol [[Turing machines]]:


Consult the [https://www.mediawiki.org/wiki/Special:MyLanguage/Help:Contents User's Guide] for information on using the wiki software.
{| class="wikitable"
|-
| BB(n,m) = Maximum number of steps done by a halting m-symbol [[Turing machine]] with n states starting from all-0 memory tape
|}


== Getting started ==
The busy beaver function is not computable and, few of its values are known:
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Configuration_settings Configuration settings list]
 
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:FAQ MediaWiki FAQ]
{| class="wikitable"
* [https://lists.wikimedia.org/postorius/lists/mediawiki-announce.lists.wikimedia.org/ MediaWiki release mailing list]
|+ Small busy beaver values
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Localisation#Translation_resources Localise MediaWiki for your language]
|-
* [https://www.mediawiki.org/wiki/Special:MyLanguage/Manual:Combating_spam Learn how to combat spam on your wiki]
|  || 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)]] > 10^^15
|-
| 3-symbol  || [[BB(2,3)]] = 38 || [[BB(3,3)]] > 10^17 || [[BB(4,3)]] > 10^14072 || --- || ---
|-
| 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 || --- || --- || --- || ---
 
|}
 
 
==Notes==
<references />

Revision as of 09:26, 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:

Small busy beaver values
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) > 10^^15
3-symbol BB(2,3) = 38 BB(3,3) > 10^17 BB(4,3) > 10^14072 --- ---
4-symbol BB(2,4) = 3,932,964 BB(3,4) > 2(^15)5 + 14 --- --- ---
5-symbol BB(2,5) > 6.5 × 10^38033 --- --- --- ---


Notes

  1. ↑ 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
  2. ↑ 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.
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Main_Page&oldid=52"