0,1

As defined by Delahaye and Zenil, the function D(n) is the linear concatenation of the output distribution of all the binary strings produced by all n-state 2-symbol Turing machines from an empty tape before halting (non-halting machines are dismissed).

The output strings are grouped and ordered by frequency, from high to less, or lexicographical if the strings had the same frequency. D(n) as a function from n, the number of states of the Turing machines, to D(n) the output distribution of all n-state Turing machines, is evidently non computable, but we have computed D(n) up to n=4.

However, lower bounds can be calculated for few states. Here we provide the sequence D(n) up to n=3. The properties of this function are similar to the properties of Sigma(n) and S(n) as defined for the busy beaver problem, for which values are also known up to n=4.

It is followed the same standard formalism of Turing machines followed in the busy beaver competition, namely Turing machines with a single bidirectional unbounded tape with a head able to write 0 or 1 and move to the left or to the right (or none if halted).

J. P. Delahaye and H. Zenil, "On the Kolmogorov-Chaitin complexity for short sequences,"Randomness and Complexity: From Leibniz to Chaitin, edited by C.S. Calude, World Scientific, 2007.

J. P. Delahaye and H. Zenil, "Towards a stable definition of Kolmogorov-Chaitin complexity," to appear in Fundamenta Informaticae, 2009.

T. Rado, On non-computable functions, Bell System Tech. J., 41 (1962), 877-884.

Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008, Table of n, a(n) for n = 0..735

Author?, The experimental AIT project

Author?, The smallest universal Turing machine implementation contest

D(n) = S(T(n),i) with i the index of the n-state Turing machine from 1 to [4n+2]^(2n), S the output frequency distribution sorting the outputs from high to less frequency and n the number of states of the Turing machine from n=1 to infinity. The number of Turing machines for n = {1, 2, 3, 4} is therefore: {36, 10000, 7529536, 11019960576}

a(1) = 0 and a(2) = 1 because out of twelve 1-state 2-symbol Turing machines that halt, six produce the string 0 and the other six produce the string 1. a(5) = 0 because it is the first bit of the third most frequent string produced by one of the 3044 2-state 2-symbol Turing machines that halt.

S[n_] := n /. Dispatch[{{1, 1}, {2, 6}, {3, 21}, {4, 107}} /. {a_, b_} :> Rule[a, b]]; TMrule[n_, {s_, k_}] := Flatten[MapIndexed[ With[{q = Quotient[ #1, k]}, {1, -1} #2 + {0, k} -> {Quotient[q + 1, 2], Mod[ #1, k], If[q == 0, 0, 2 Mod[q, 2] - 1]}] &, Partition[IntegerDigits[n, 2 s k + k, s k], k], {2}]] Tally[Last /@ Last /@ Pick[Join[ Table[ TuringMachine[TMrule[n, {2, k}], {1, {{}, 0}}, S[k]], {i, NumberOfReducedTuringMachines[k]}], Table[ TuringMachine[TMrule[n, {2, k}], {1, {{}, 1}}, S[k]], {i, NumberOfReducedTuringMachines[k]}]], MemberQ[ #, "H"] & /@ Union /@ Flatten /@ Map[First, res, {2}]]]

Sequence in context: A127266 A083923 A101309 this_sequence A073424 A135993 A145573

Adjacent sequences: A141471 A141472 A141473 this_sequence A141475 A141476 A141477

nonn

Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008