|
|
A004147
|
|
Number of n-state Turing machines which halt.
(Formerly M5233)
|
|
6
|
|
|
|
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
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,hard,bref
|
|
AUTHOR
|
|
|
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 4-state machines up to 107 steps, Mar 05 2016
|
|
STATUS
|
approved
|
|
|
|