|
| |
|
|
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 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).
|
|
|
REFERENCES
|
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.
T. Rado, On non-computable functions, Bell System Tech. J., 41 (1962), 877-884.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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}
|
|
|
EXAMPLE
|
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.
|
|
|
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.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008
|
|
|
STATUS
|
approved
|
| |
|
|
