Editing Busy beaver (section)

==References==
{{refbegin}}
* {{cite journal | last = Radó | first = Tibor | author-link = Tibor Radó | url = https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf | title = On non-computable functions | journal = [[Bell System Technical Journal]] | volume = 41 | issue = 3 | date = May 1962 | pages = 877–884 | doi = 10.1002/j.1538-7305.1962.tb00480.x | archive-date = 2021-10-12 | access-date = 2022-07-07 | archive-url = https://web.archive.org/web/20211012165438/http://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf | url-status = live }}
*: This is where Radó first defined the busy beaver problem and proved that it was uncomputable and grew faster than any computable function.
* {{cite journal | last1 = Lin | first1 = Shen | last2 = Radó | first2 = Tibor | author-link2 = Tibor Radó | title = Computer Studies of Turing Machine Problems | journal = [[Journal of the ACM]] | volume = 12 | issue = 2 | date = April 1965 | pages = 196–212 | doi = 10.1145/321264.321270 | s2cid = 17789208 | url = https://rave.ohiolink.edu/etdc/view?acc_num=osu1486554418657614 | doi-access = free }}
*: The results of this paper had already appeared in part in Lin's 1963 doctoral dissertation, under Radó's guidance.  Lin & Radó prove that Σ(3) = 6 and ''S''(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt within 21 steps will never halt. (Most are proven automatically by a computer program, however 40 are proven by human inspection.) 
* {{cite journal | last1 = Brady | first1 = Allen H. | title = The determination of the value of Rado's noncomputable function Σ(''k'') for four-state Turing machines | journal = [[Mathematics of Computation]] | volume = 40 | issue = 162 |date=April 1983 | pages = 647–665 | jstor = 2007539 | doi = 10.1090/S0025-5718-1983-0689479-6 | doi-access = free }}
*: Brady proves that Σ(4) = 13 and ''S''(4) = 107. Brady defines two new categories for non-halting 3-state 2-symbol Turing Machines: Christmas Trees and Counters. He uses a computer program to prove that all but 27 machines which run over 107 steps are variants of Christmas Trees and Counters which can be proven to run infinitely. The last 27 machines (referred to as holdouts) are proven by personal inspection by Brady himself not to halt.
* {{cite journal | last1 = Machlin | first1 = Rona | last2 = Stout | first2 = Quentin F. | url = https://eecs.umich.edu/~qstout/abs/busyb.html | title = The complex behavior of simple machines | journal = [[Physica (journal)|Physica D: Nonlinear Phenomena]] | volume = 42 | issue = 1–3 | date = June 1990 | pages = 85–98 | doi = 10.1016/0167-2789(90)90068-Z | hdl = 2027.42/28528 | bibcode = 1990PhyD...42...85M | hdl-access = free | archive-date = 2012-01-30 | access-date = 2022-07-07 | archive-url = https://web.archive.org/web/20120130170451/http://www.eecs.umich.edu/%7Eqstout/abs/busyb.html | url-status = live }}
*: Machlin and Stout describe the busy beaver problem and many techniques used for finding busy beavers (which they apply to Turing Machines with 4-states and 2-symbols, thus verifying Brady's proof). They suggest how to estimate a variant of Chaitin's halting probability (Ω).
* {{cite journal | last1 = Marxen | first1 = Heiner | last2 = Buntrock | first2 = Jürgen | title = Attacking the Busy Beaver 5 | journal = [[European Association for Theoretical Computer Science|Bulletin of the EATCS]] | volume = 40 | date = February 1990 | pages = 247–251 | url = https://turbotm.de/~heiner/BB/mabu90.html | access-date = 2020-01-19 | archive-url = https://web.archive.org/web/20061009135243/https://drb.insel.de/~heiner/BB/mabu90.html | archive-date = 2006-10-09 | url-status = live }}
*: Marxen and Buntrock demonstrate that Σ(5)&nbsp;≥&nbsp;4098 and ''S''(5)&nbsp;≥&nbsp;{{val|47176870}} and describe in detail the method they used to find these machines and prove many others will never halt.
* {{cite conference | last1 = Green | first1 = Milton W. | year = 1964 | title = A Lower Bound on Rado's Sigma Function for Binary Turing Machines | url = https://computer.org/csdl/proceedings/focs/1964/5428/00/index.html | conference = 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design | pages = 91–94 | doi = 10.1109/SWCT.1964.3 | access-date = 2022-07-07 | archive-date = 2019-02-03 | archive-url = https://web.archive.org/web/20190203080735/https://www.computer.org/csdl/proceedings/focs/1964/5428/00/index.html | url-status = live }}
*: Green recursively constructs machines for any number of states and provides the recursive function that computes their score (computes σ), thus providing a lower bound for Σ. This function's growth is comparable to that of [[Ackermann's function]].
* {{cite journal | last = Dewdney | first = Alexander K. |author-link = Alexander Dewdney | title = A computer trap for the busy beaver, the hardest working Turing machine | journal = [[Scientific American]] | volume = 251 | issue = 2 | pages = 10–17 | year = 1984 }}
*: Busy beaver programs are described by [[Alexander Dewdney]] in ''Scientific American'', August 1984, pages 19–23, also March 1985 p.&nbsp;23 and [https://web.archive.org/web/20100709121641/https://grail.cba.csuohio.edu/~somos/busy.html#dewd April 1985 p. 30].
* {{cite book | last = Chaitin | first = Gregory J. | author-link = Gregory Chaitin | chapter = Computing the Busy Beaver Function | editor1-first = T. M. | editor1-last = Cover | editor2-first = B. | editor2-last = Gopinath | title = Open Problems in Communication and Computation | publisher = Springer | year = 1987 | pages = 108–112 | chapter-url = https://cs.auckland.ac.nz/~chaitin/bellcom.pdf | isbn = 978-0-387-96621-2 | access-date = 2022-07-07 | archive-date = 2017-12-30 | archive-url = https://web.archive.org/web/20171230195953/https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf | url-status = dead }}
* {{cite book | last = Brady | first = Allen H. | chapter = The Busy Beaver Game and the Meaning of Life | pages = 237–254 | editor1-last = Herken | editor1-first = Rolf | title = The Universal Turing Machine: A Half-Century Survey | edition = 2nd | year = 1995 | publisher = Springer-Verlag | location = Wien, New York |isbn = 978-3-211-82637-9 }}
*: Wherein Brady (of 4-state fame) describes some history of the beast and calls its pursuit "The Busy Beaver Game". He describes other games (e.g. [[cellular automata]] and [[Conway's Game of Life]]). Of particular interest is "The Busy Beaver Game in Two Dimensions" (p.&nbsp;247). With 19 references.
* {{cite book | author-link = Taylor L. Booth | first = Taylor L. | last = Booth | title = Sequential Machines and Automata Theory | publisher = Wiley | location =  New York | year = 1967 | isbn = 978-0-471-08848-6 }}
*: Cf Chapter 9, Turing Machines. A difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. A reference in Booth attributes busy beaver to Rado. Booth also defines Rado's busy beaver problem in "home problems" 3, 4, 5, 6 of Chapter 9, p.&nbsp;396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n."
*{{cite journal | first1 = A. M. | last1 = Ben-Amram | first2 = H. | last2 = Petersen | title = Improved Bounds for Functions Related to Busy Beavers | journal = [[Theory of Computing Systems]] | volume = 35 | pages = 1–11 | year =  2002 | doi = 10.1007/s00224-001-1052-0 | citeseerx = 10.1.1.136.5997 | s2cid = 10429773 }}
*: Improved bounds.
* {{cite conference | first1 = G. | last1 = Lafitte | first2 = C. | last2 = Papazian | citeseerx = 10.1.1.104.3021 | title = The fabric of small Turing machines | book-title = Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe |date=June 2007 | pages = 219–227 }}
*: This article contains a complete classification of the 2-state, 3-symbol Turing machines, and thus a proof for the (2, 3) busy beaver: Σ(2, 3) = 9 and S(2, 3) = 38.
* {{cite book | first1 = George S. | last1 = Boolos | first2 = John P. | last2 = Burgess | first3 = Richard C. | last3 = Jeffrey | title = Computability and Logic | url = https://archive.org/details/computabilitylog0000bool | url-access = registration | edition = Fifth | year = 2007 | publisher = Cambridge University Press | isbn = 978-0-521-87752-7 }}
* {{cite thesis | first1 = Pavel | last1 = Kropitz | title = Problém Busy Beaver | degree = Bachelor | year = 2010 | publisher = Charles University in Prague | language = sk | url = https://dspace.cuni.cz/bitstream/handle/20.500.11956/37142/BPTX_2007_1__0_229600_0_49210.pdf?sequence=1&isAllowed=y}}
*: This is the description of ideas, of the algorithms and their implementation, with the description of the experiments examining 5-state and 6-state Turing machines by parallel run on 31 4-core computer and finally the best results for 6-state TM.
{{refend}}