login
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

%I #8 Mar 18 2020 16:36:54

%S 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,

%T 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,

%U 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

%N Minimal number of states required for a 2-symbol, 5-tuple Turing machine that takes n steps on an initially blank tape before halting.

%C 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).

%C 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

%H Martin Fuller, <a href="/A125269/b125269.txt">Table of n, a(n) for n = 1..626</a>

%H Martin Fuller, <a href="/A125269/a125269.txt">Illustration file listing a Turing machine for each n</a>

%H H. Marxen, <a href="http://turbotm.de/~heiner/BB/">Info on the Busy Beaver problem</a>

%Y Cf. A060843, A052200.

%K nice,nonn

%O 1,2

%A Dustin Wehr (robert.wehr(AT)mail.mcgill.ca), Jan 16 2007, Jan 28 2007

%E More terms from _Martin Fuller_, Feb 14 2007