cp's OEIS Frontend

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.

%I A125269 #8 Mar 18 2020 16:36:54
%S A125269 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 A125269 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 A125269 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 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.
%C A125269 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 A125269 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 A125269 Martin Fuller, <a href="/A125269/b125269.txt">Table of n, a(n) for n = 1..626</a>
%H A125269 Martin Fuller, <a href="/A125269/a125269.txt">Illustration file listing a Turing machine for each n</a>
%H A125269 H. Marxen, <a href="http://turbotm.de/~heiner/BB/">Info on the Busy Beaver problem</a>
%Y A125269 Cf. A060843, A052200.
%K A125269 nice,nonn
%O A125269 1,2
%A A125269 Dustin Wehr (robert.wehr(AT)mail.mcgill.ca), Jan 16 2007, Jan 28 2007
%E A125269 More terms from _Martin Fuller_, Feb 14 2007