

A141474


Concatenated and flattened output distributions of the Turing machines described in the comments lines.


1



0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,1


COMMENTS

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 nstate 2symbol Turing machines from an empty tape before halting (nonhalting 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 nstate Turing machines, is evidently noncomputable, 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).


REFERENCES

J. P. Delahaye and H. Zenil, "On the KolmogorovChaitin complexity for short sequences,"Randomness and Complexity: From Leibniz to Chaitin, edited by C.S. Calude, World Scientific, 2007.
T. Rado, On noncomputable functions, Bell System Tech. J., 41 (1962), 877884.


LINKS



FORMULA

D(n) = S(T(n),i) with i the index of the nstate 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}


EXAMPLE

a(1) = 0 and a(2) = 1 because out of twelve 1state 2symbol 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 2state 2symbol Turing machines that halt.


MATHEMATICA

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}]]]


CROSSREFS



KEYWORD

nonn


AUTHOR

Hector Zenil (hector.zenilchavez(AT)malix.univparis1.fr), Aug 09 2008


STATUS

approved



