cp's OEIS Frontend

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

%I A052200 #38 Nov 01 2024 21:04:28
%S A052200 1,64,20736,16777216,25600000000,63403380965376,232218265089212416,
%T A052200 1180591620717411303424,7958661109946400884391936,
%U A052200 68719476736000000000000000000,739696442014594807059393047166976,9711967541295580042210555933809967104,152784834199652075368661148843397208866816
%N A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.
%C A052200 T in T_(n, k) is a Turing machine with n states and k symbols;
%C A052200 States q, q+ in set Q_n of n distinct states (plus the Halt state;)
%C A052200 Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)
%C A052200 Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)
%C A052200 + suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).
%C A052200 This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - _Michael Joseph Halm_, Apr 29 2003
%C A052200 From _Daniel Forgues_, Jun 06 2011: (Start)
%C A052200 RE: Busy beaver halting Turing machines:
%C A052200 H in H_(n, k) is a halting* Turing machine with n states and k symbols;
%C A052200 * (on a blank tape, all 0's, as input)
%C A052200 sigma(H) is the number of non-blank symbols left on the tape by H;
%C A052200 s(H) is the number of steps (or shifts in our case) taken by H;
%C A052200 Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
%C A052200 S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
%C A052200 Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)
%C A052200 This sequence also counts machines with unreachable states, and all (up to (n-1)!) permutations of non-start states, which don't affect behavior. In contrast, A107668 only counts state graphs reaching all n states in canonical order. - _John Tromp_, Oct 17 2024
%H A052200 J. P. Jones, <a href="https://www.jstor.org/stable/2319560">Recursive undecidability - an exposition</a>, Amer. Math. Monthly, 81 (1974), 724-738.
%H A052200 Michael Somos, <a href="https://grail.eecs.csuohio.edu/~somos/busy.html">The Busy Beaver Problem</a>
%H A052200 OEIS Wiki, <a href="http://oeis.org/wiki/Busy_Beaver_numbers">Busy Beaver numbers</a>
%H A052200 <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>
%F A052200 a(n) = (4*(n+1))^(2*n).
%e A052200 a(1) = 64 = (4*1+4)^(2*1) = 8^2.
%t A052200 A052200[n_]:=(4(n+1))^(2n); Array[A052200,20,0] (* _Paolo Xausa_, May 21 2023 *)
%Y A052200 Cf. A028444, A004147, A060843, A107668.
%K A052200 nonn,easy
%O A052200 0,2
%A A052200 _Michael Somos_, Jan 28 2000
%E A052200 Entry revised by _N. J. A. Sloane_, Feb 08 2007
%E A052200 Edited by _Daniel Forgues_, Mar 25 2010