|
| |
|
|
A004147
|
|
Number of n-state Turing machines which halt.
(Formerly M5233)
|
|
3
| | |
|
|
|
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
| J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| 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: A159679 A139568 A139294 * A069444 A187240 A062315
Adjacent sequences: A004144 A004145 A004146 * A004148 A004149 A004150
|
|
|
KEYWORD
| nonn,nice,hard,bref
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007
|
| |
|
|
