For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

For example, if a cluster of nodes has a certain number of connections to the rest of the network, then it cannot be replaced by a cluster which has a different number of connections.

Material for this chapter Like the rest of this book, this chapter is strongly based on my personal work and observations.

Rest[list]/#1) &, Apply[ ExtendedGCD, Drop[list, -1]]]}, {Mod[ α , #], #} &[ Fold[GCD[#1, If[#1  0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{ α , -1}, list]]]] With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]] .

Some sections of chapters (usually later ones) were added well after the rest.

And so to make cryptography work it must be the case that even if one knows certain features or parts of the encrypting sequence it is still difficult to deduce the original key or otherwise to generate the rest of the sequence.

A coin spun on a table can rotate several hundred times before falling over and coming to rest.

and from the key the whole of the rest of the encrypting sequence can immediately be generated.

Conway considered fraction systems based on rules of the form FSEvolveList[fracs_, init_, t_] := NestList[First[Select[fracs #, IntegerQ, 1]] &, init, t] With the choice fracs = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/ 23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1} starting at 2 the result for Log[2, list] is as shown below, where Rest[Log[2, Select[list, IntegerQ[Log[2, #]] &]]] gives exactly the primes.

Substitution systems in which all replacements are done that are found to fit in a left-to-right scan can be implemented as follows GSSEvolveList[rule_, s_, n_] := NestList[GSSStep[rule, #] &, s, n] GSSStep[rule_, s_] := g[rule, s, f[StringPosition[s, Map[First, rule]]]] f[{ }] = { }; f[s_] := Fold[If[Last[Last[#1]] ≥ First[#2], #1, Append[#1, #2]]&, {First[s]}, Rest[s]] g[rule_, s_, { }] := s; g[rule_, s_, pos_] := StringReplacePart[ s, Map[StringTake[s, #] &, pos] /. rule, pos] with rules given as {"ABA"  "BAAB", "BBBB"  "AA"} .