|
%I M5233 #28 May 17 2023 14:41:24
%S 32,9784,7571840,11140566368
%N Number of n-state Turing machines which halt.
%C This sequence is noncomputable, because it could be used to solve the halting problem. In fact, it is of the same degree of difficulty as the halting problem. - David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H J. P. Jones, <a href="http://www.jstor.org/stable/2319560">Recursive undecidability - an exposition</a>, Amer. Math. Monthly, 81 (1974), 724-738.
%H H. Marxen, <a href="http://turbotm.de/~heiner/BB/">Busy Beaver</a>
%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/bb.html">Busy Beaver Turing Machine</a>
%H Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/busy.html">Busy Beaver</a>
%H <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>
%Y Cf. A028444, A052200.
%K nonn,nice,hard,bref
%O 1,1
%A _N. J. A. Sloane_
%E More terms from David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007
%E a(4) from _Jonathan Lee_, who enumerated all 25.6 billion 4-state machines up to 107 steps, Mar 05 2016
| 