Given an original DNF list s , this can be done using PI[s, n] : PI[s_, n_] := Union[Flatten[ FixedPointList[f[Last[#], n] &, {{}, s}] 〚 All, 1 〛 , 1]] g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i]  1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]] f[s_, n_] := With[ {w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[ Select[s, Count[#, 1]  i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest  MatchQ], w}] The minimal DNF then consists of a collection of these prime implicants. … Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF: QM[s_, p_] := First[Sort[Map[p 〚 # 〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]] h[i_, r_, t_] := Flatten[Map[h[Join[i, r 〚 # 〛 ], Drop[r, #], Delete[Drop[t, {}, #], Position[t 〚 All, # 〛 ], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1] h[i_, _, {}] := {i} The number of steps required in this procedure can increase exponentially with the length of p .

And between any two universal systems programs can differ in length by at most a constant: for one can always just add a fixed interpreter program to the programs for one system in order to make them run on the other system. … If one considers all 2 n possible sequences (say of 0's and 1's) of length n then it is straightforward to see that most of them must be more or less algorithmically random. For in order to have enough programs to generate all 2 n sequences most of the programs one uses must themselves be close to length n .

The basic idea is to encode the list of values of all the registers in the multiregister machine in the single number given by RMEncode[list_] := Product[Prime[j]^list 〚 j 〛 , {j, Length[list]}] and then to have this number be the value at appropriate steps of the first register in the 2-register machine. The program in the multiregister machine can be converted to a program for the 2-register machine according to RMToRM2[prog_] := Module[{segs, adrs}, segs = MapIndexed[seg, prog]; adrs = FoldList[Plus, 1, Map[Length, segs]]; MapIndexed[#1 /.

Rules such as {{1, 0}, {0, 1}} and {{1, 1}, {0}} therefore yield repetitive behavior with sequences of limited length. Note that if all blocks in a cyclic tag system with n blocks have lengths divisible by n , then one can tell in advance on which steps blocks will be added, and the overall behavior obtained must correspond to a neighbor-independent substitution system.

Lengths of [number] representations (a) n , (b) Floor[Log[2, n] + 1] , (c) Tr[FixedPointList[Max[0, Ceiling[Log[2, #]]] &, n + 2]] - n - 3 , (d) 2 Ceiling[Log[3, 2n + 1]] , (e) Floor[Log[GoldenRatio, √ 5 (n + 1/2)]] .

The sequence {1, 2, 2, 1, 1, 2, …} defined by the property list  Map[Length, Split[list]] was suggested as a mathematical puzzle by William Kolakoski in 1965 and is equivalent to Join[{1, 2}, Map[First, CTEvolveList[{{1}, {2}}, {2}, t]]] It is known that this sequence does not repeat, contains no more than two identical consecutive blocks, and has at least very close to equal numbers of 1's and 2's.

Rule 30 inversion The total numbers of sequences for t from 1 to 15 not yielding stripes of heights 1 and 2 are respectively {1, 2, 2, 3, 3, 6, 6, 10, 16, 31, 52, 99, 165, 260} {2, 5, 8, 14, 23, 40, 66, 111, 182, 316, 540, 921, 1530, 2543, 4122} The sideways evolution of rule 30 discussed on page 601 implies that if one fills cells from the left rather than the right then some sequence of length t + 1 will always yield any given stripe of height t .

But in 1977 Gennadií Makanin gave a complicated algorithm that solves the problem completely in a finite number of steps (though in general triple exponential in the length of the equation).

The fraction of possible register machines that do this starting from initial condition {1, {0, 0}} decreases steadily with program length n , reaching about 0.76 for n = 8 .

One possible such ordering for numbers with a total of m digits is GrayCode[m_] := Nest[Join[#, Length[#] + Reverse[#]] &, {0}, m] The succession of sizes and digit sequences of numbers ordered in this way are shown below.