Generating functions [for regular languages] The sequences in a regular language can be thought of as corresponding to products of non-commuting variables that appear as coefficients in a formal power series expansion of a generating function.

And unlike for quantum electrodynamics there did not seem to be only a finite number of these—that could be removed by renormalization. … Analytical approaches (that happened to be like 0D string theory) were also found for 2D discrete spacetimes (compare page 1038 )—but they were not successfully extended to higher dimensions. … If one computes the product of Exp[  (j 1 + j 2 - j 3 )] for all triangles, then it turns out for example that this quantity is extremized exactly when the whole surface is flat.

Fibonacci[n] can be obtained in many ways: • (GoldenRatio n - (-GoldenRatio) -n )/ √ 5 • Round[GoldenRatio n / √ 5 ] • 2 1 - n Coefficient[(1 + √ 5 ) n , √ 5 ] • MatrixPower[{{1, 1}, {1, 0}}, n - 1] 〚 1, 1 〛 • Numerator[NestList[1/(1 + #)&, 1, n]] • Coefficient[Series[1/(1 - t - t 2 ), {t, 0, n}], t n - 1 ] • Sum[Binomial[n - i - 1, i], {i, 0, (n - 1)/2}] • 2 n - 2 - Count[IntegerDigits[Range[0, 2 n - 2 ], 2], {___, 1, 1, ___}] A fast method for evaluating Fibonacci[n] is First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]] f[{a_, b_, s_}, 0] = {a (a + 2b), s + a (2a - b), 1} f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -1} Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths. … Their recurrence relation appears to have been understood from the early 1600s, but it has only been in the past very few decades that they have in general become widely discussed. … It appears to be zero only when n is of the form 5 m or 12q , where q is not prime ( q > 5 ).

The system generates a dark gray stripe on the left at all positions that correspond to any product of numbers other than 1. White gaps then remain at positions that correspond to the prime numbers 2, 3, 5, 7, 11, 13, 17, etc.

General associative [cellular automaton] rules With a cellular automaton rule in which the new color of a cell is given by f[a 1 , a 2 ] (compare page 886 ) it turns out that the pattern generated by evolution from a single non-white cell is always nested if the function f has the property of being associative or Flat . … The result can also be generalized to cellular automata with basic rules involving more than two elements—since if f is Flat , f[a 1 , a 2 , a 3 ] is always just f[f[a 1 , a 2 ], a 3 ] . … (In general f can correspond to an almost arbitrary semigroup, but with a single initial element only a cyclic subgroup of it is ever explored.)

Logic circuits [from cellular automata] The rules for the cellular automaton shown here are {{0, 1, 1 | 3}  1, {0, 3, 3}  3, {1, 0, 0 | 1 | 3}  1, {1, 1, 3}  4, {1, 3, 0}  3, {1, 3, 3}  2, {2, 1, 3}  3, {2, 3, 0}  2, {2, 0, _}  4, {3, 3, 0}  3, {4, 0, 0 | 1 | 2 | 4}  2, {4, 3, 3}  3, {4, 1, 3}  1, {4, 3, 0}  4, {_, _, _}  0} The initial conditions are given by Flatten[Block[{And, Or}, Map[{0, 2 (# + 1)} &, expr, {-1}] //. {!x_  {0, x, 0}, And[x__]  {0, 0, 1, 0, x, 1, 3, 0, 0}, Or[x__]  {0, 0, 1, 0, x, 0, 1, 3, 0}}]] and in terms of these initial conditions the cellular automaton must be run for Length[list //. {0, x__}  {x}] - 1 steps in order to find the result.

The word problem then asks if a given product of such generators is equal to the identity element. … Even if a group ultimately has only a finite number of distinct elements, its word problem (with elements specified as products of generators) may still be undecidable. … (In general s k+4 generators and 5 s k+2 relations are needed.)

LFSR sequences Often referred to as pseudonoise or PN sequences, maximal length linear feedback shift register sequences have repetition period 2 n - 1 and are generated by shift registers that go through all their possible states except the one consisting of all 0's, as discussed on page 974 . … (Note that only a small fraction of all possible sequences with this property can be generated by LFSRs.) … This quantity is -1 for all nonzero m for PN sequences (so that all but the first component in Abs[Fourier[(-1) list ]] 2 are equal), but has mean 0 for truly random sequences.

({a_, b_, c_}  d_)  ({1, 2a, 2b, 2c}  {2d, 1, 2b, 2c}), {{1, 0, 0}  {0, 0}, {0}  {1, 0, 0, 0}}] The initial condition {0, 0, 2, 0, 0} for the sequential substitution system corresponds to a single black cell surrounded by white cells in the cellular automaton.

The arrangement of triangles at step t can be obtained from a substitution system according to With[{ ϕ = GoldenRatio}, Nest[# /. a[p_, q_, r_]  With[{s = (p + ϕ q) (2 - ϕ )}, {a[r, s, q], b[r, s, p]}] /. b[p_, q_, r_]  With[{s = (p + ϕ r) (2 - ϕ )}, {a[p, q, s], b[ r, s, q]}] &, a[{1/2, Sin[2 π /5] ϕ }, {1, 0}, {0, 0}], t]] This pattern can be viewed as generalizations of the pattern generated by the 1D Fibonacci substitution system (c) on page 83 . … Penrose tilings can be obtained by looking at how a 2D plane with slopes based on GoldenRatio cuts through a lattice of hypercubes in 5D. … Despite some confusion in the literature, however, this procedure can reproduce only a tiny fraction of all possible nested patterns.