A389270 - OEIS

%I #44 Feb 23 2026 14:49:55

%S 0,7,2,7,4,3,6,11,8,15,10,15,12,15,14,19,16,23,18,23,20,19,22,27,24,

%T 31,26,31,28,31,30,35,32,39,34,39,36,35,38,43,40,47,42,47,44,47,46,51,

%U 48,55,50,55,52,51,54,59,56,63,58,63,60,63,62,67,64,71,66

%N Number computed by Wolfram's 3-state 2-symbol Turing machine 1342057 when started with n on the tape.

%C Machine 1342057 computes this function with asymptotic runtime 4^n, but there exists a 4-state 2-symbol machine (number 1517414255) which computes this function with worst-case runtime of 7.

%H Sean A. Irvine, <a href="/A389270/b389270.txt">Table of n, a(n) for n = 1..1000</a>

%H Stephen Wolfram, <a href="https://writings.stephenwolfram.com/2026/01/p-vs-np-and-the-difficulty-of-computation-a-ruliological-approach/">P vs. NP and the Difficulty of Computation: A Ruliological Approach</a>, 2026.

%t With[{lim = 67, len = 2^20}, PacletSymbol["WolframInstitute/TuringMachine", "OneSidedTuringMachineFunction"][{1342057, 3, 2}, {1, lim}, len]] (* _Michael De Vlieger_, Feb 22 2026 *)

%Y Cf. A393542, A392245.

%K nonn

%O 1,2

%A _Sean A. Irvine_, Feb 22 2026