|
Search: id:A004147
|
|
|
| A004147 |
|
Number of n-state Turing machines which halt.
(Formerly M5233)
|
|
+0
4
|
| |
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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 this_sequence A069444 A062315 A159384
Adjacent sequences: A004144 A004145 A004146 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
