

A004147


Number of nstate Turing machines which halt.
(Formerly M5233)


4




OFFSET

1,1


COMMENTS

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


REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=1..4.
J. P. Jones, Recursive undecidability  an exposition, Amer. Math. Monthly, 81 (1974), 724738.
H. Marxen, Busy Beaver
M. Somos, Busy Beaver Turing Machine
M. Somos, Busy Beaver
Index entries for sequences related to Busy Beaver problem


CROSSREFS

Cf. A028444, A052200.
Sequence in context: A231035 A213813 A241369 * A212800 A214387 A069444
Adjacent sequences: A004144 A004145 A004146 * A004148 A004149 A004150


KEYWORD

nonn,nice,hard,bref


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007
a(4) from Jonathan Lee, who enumerated all 25.6 billion 4state machines up to 107 steps, Mar 05 2016


STATUS

approved



