%I A141474
%S A141474 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,
%T A141474 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,
%U A141474 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 A141474 Concatenated and flattened output distributions of the Turing machines 
               described in the comments lines.
%C A141474 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 A141474 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 A141474 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 A141474 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 A141474 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 A141474 J. P. Delahaye and H. Zenil, "Towards a stable definition of Kolmogorov-Chaitin 
               complexity," to appear in Fundamenta Informaticae, 2009.
%D A141474 T. Rado, On non-computable functions, Bell System Tech. J., 41 (1962), 
               877-884.
%H A141474 Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008, 
               <a href="b141474.txt">Table of n, a(n) for n = 0..735</a>
%H A141474 Author?, <a href="http://www.mathrix.org/experimentalAIT/">The experimental 
               AIT project</a>
%H A141474 Author?, <a href="http://www.mathrix.org/experimentalAIT/TuringMachine.html">
               The smallest universal Turing machine implementation contest</a>
%F A141474 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 A141474 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 A141474 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}]]]
%Y A141474 Sequence in context: A127266 A083923 A101309 this_sequence A073424 A135993 
               A145573
%Y A141474 Adjacent sequences: A141471 A141472 A141473 this_sequence A141475 A141476 
               A141477
%K A141474 nonn
%O A141474 0,1
%A A141474 Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008