|
|
A125269
|
|
Minimal number of states required for a 2-symbol, 5-tuple Turing machine that takes n steps on an initially blank tape before halting.
|
|
1
|
|
|
1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 4, 4, 5, 5, 4, 5, 5, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. The terms with values 1,2,3 were computed by exhaustive search. The terms with value 4 were inferred from knowing that they are greater than 3 and from the observation that for all n, a(n+1) <= a(n) + 1 (an easy construction). Using exhaustive search, may be able to extend the sequence to (most of) the terms up to and a bit beyond a(107) = 4, but going much further would likely require a more sophisticated method (see A052200).
If BB(n) = A060843(n), then a(BB(n)) = n and that is the last occurrence of n in this sequence. a(n) will not become monotonic; if it did, we could compute BB(n), since a(n) is computable. a(n) diverges properly, but does so very slowly. a(n+1) <= a(n) + 1 (an easy construction). - Martin Fuller, Feb 14 2007
|
|
LINKS
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
Dustin Wehr (robert.wehr(AT)mail.mcgill.ca), Jan 16 2007, Jan 28 2007
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|