But it is straightforward to define versions of entropy that take account of probabilities—and indeed the closest analog to the usual entropy in physics or information theory is obtained by taking the probabilities p[i] for the k n blocks of length n (assuming k colors), then constructing -Limit[Sum[p[i] Log[k, p[i]], {i, k n }]/n, n  ∞ ] I have tended to call this quantity measure entropy, though in other contexts, it is often just called entropy or information, and is sometimes called information dimension.

To recognize a regular crystal as not being a carefully cut artifact can take specific knowledge.

But I suspect that in the end it will take only a surprisingly simple polynomial, perhaps with just three variables and fairly low degree.

An example with 8 registers and 41 instructions is: or {d[4, 40], i[5], d[3, 9], i[3], d[7, 4], d[5, 14], i[6], d[3, 3], i[7], d[6, 2], i[6], d[5, 11], d[6, 3], d[4, 35], d[6, 15], i[4], d[8, 16], d[5, 21], i[1], d[3, 1], d[5, 25], i[2], d[3, 1], i[6], d[5, 32], d[1, 28], d[3, 1], d[4, 28], i[4], d[6, 29], d[3, 1], d[5, 24], d[2, 28], d[3, 1], i[8], i[6], d[5, 36], i[6], d[3, 3], d[6, 40], d[4, 3]} Given any register machine, one first applies the function RMToRM2 from page 1114 , then takes the resulting program and initial condition and finds an initial condition for the URM using R2ToURM[prog_, init_] := Join[init, With[ {n = Length[prog]}, {1 + LE[Reverse[prog] /.

And if the output from a computation can be of size 2 n then this will normally take at least 2 n steps to generate.

And if one always does computations using systems that have only nearest-neighbor rules then just combining 2t + 1 bits of information can take up to t steps—even if the bits are combined in a way that is not computationally irreducible.

= {}) &];]] ReverseRule[a_  b_, {i_}] := {___, {s[x___, b, y___], {u___}}, ___}  {s[x, a, y], {i, u}} /; FreeQ[s[x], s[a]] In general, there will in principle be more than one such list, and to pick the appropriate list in a practical situation one normally takes the rules of the language to apply with a certain precedence—which is how, for example, x + y z comes to be interpreted in Mathematica as Plus[x, Times[y, z]] rather than Times[Plus[x, y], z] .

Fractal dimensions [of additive cellular automata] The total number of nonzero cells in the first t rows of the pattern generated by the evolution of an additive cellular automaton with k colors and weights w (see page 952 ) from a single initial 1 can be found using g[w_, k_, t_] := Apply[Plus, Sign[NestList[Mod[ ListCorrelate[w, #, {-1, 1}, 0], k] &, {1}, t - 1]], {0, 1}] The fractal dimension of this pattern is then given by the large m limit of Log[k,g[w, k,k m + 1 ]/g[w, k, k m ]] When k is prime it turns out that this can be computed as d[w_, k_:2] := Log[k,Max[Abs[Eigenvalues[With[ {s = Length[w] - 1}, Map[Function[u, Map[Count[u, #] &, #1]], Map[Flatten[Map[Partition[Take[#, k + s - 1], s, 1] &, NestList[Mod[ListConvolve[w, #], k] &, #, k - 1]], 1] &, Map[Flatten[Map[{Table[0, {k - 1}], #} &, Append[#, 0]]] &, #]]] &[Array[IntegerDigits[#, k, s] &, k s - 1]]]]]]] For rule 90 one gets d[{1, 0, 1}] = Log[2, 3] ≃ 1.58 .

With an initial condition of n cells, this then takes roughly (100 + 35 n) t + 33 t 2 steps of combinator evolution.

Most often there are two basic rules of inference: modus ponens or detachment which uses the logic result (x ∧ x  y)  y to deduce the statement y from statements x and x  y , and substitution, which takes statements x and y and deduces x /. p  y , where p is a logical variable in x (see page 1151 ).