# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a141474 Showing 1-1 of 1 %I A141474 #13 Mar 17 2018 04:06:31 %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, %T A141474 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 A141474 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 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 T. Rado, On non-computable functions, Bell System Tech. J., 41 (1962), 877-884. %H A141474 Hector Zenil, Table of n, a(n) for n = 0..735 %H A141474 J. P. Delahaye and H. Zenil, Towards a stable definition of Kolmogorov-Chaitin complexity, arXiv:0804.3459 [cs.IT], 2008-2010; to appear in Fundamenta Informaticae, 2009. %H A141474 Hector Zenil, The experimental AIT project %H A141474 Hector Zenil, The smallest universal Turing machine implementation contest %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}]]] %K A141474 nonn %O A141474 0,1 %A A141474 Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE