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

%I #13 Mar 17 2018 04:06:31

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

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

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

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

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

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

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

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

%D 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.

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

%H Hector Zenil, <a href="/A141474/b141474.txt">Table of n, a(n) for n = 0..735</a>

%H J. P. Delahaye and H. Zenil, <a href="https://arxiv.org/abs/0804.3459">Towards a stable definition of Kolmogorov-Chaitin complexity</a>, arXiv:0804.3459 [cs.IT], 2008-2010; to appear in Fundamenta Informaticae, 2009.

%H Hector Zenil, <a href="http://www.mathrix.org/experimentalAIT/">The experimental AIT project</a>

%H Hector Zenil, <a href="http://www.mathrix.org/experimentalAIT/TuringMachine.html">The smallest universal Turing machine implementation contest</a>

%F 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}

%e 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.

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

%K nonn

%O 0,1

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