If p is a list of coordinate parameters that appear in a d -dimensional metric g , then Riemann = Table[ ∂ p 〚 j 〛 Γ 〚 i, k 〛 - ∂ p 〚 i 〛 Γ 〚 j, k 〛 + Γ 〚 i, k 〛 . … Γ 〚 i 〛 , {i, d}, {j, d}, {k, d}] where the so-called Christoffel symbol Γ ij k is Γ = With[{gi = Inverse[g]}, Table[Sum[ gi 〚 l, k 〛 ( ∂ p 〚 j 〛 g 〚 i, l 〛 + ∂ p 〚 i 〛 g 〚 j, l 〛 - ∂ p 〚 l 〛 g 〚 j, l 〛 ), {l, d}], {i, d}, {j, d}, {k, d}]]/2 There are d 4 elements in the nested lists for Riemann , but symmetries and the so-called Bianchi identity reduce the number of independent components to 1/12 d 2 (d 2 - 1) —or 20 for d = 4 .

If one has a table of choices, one can imagine generalizing this to a function of a real number.

The definition of the function f for rule 90 that we gave above is essentially just a look-up table.

With the state of a 2-color tag system encoded as an integer according to FromDigits[Reverse[list] + 1, 3] the following takes the rule for any such tag system (in the first form from page 894 ) and yields a primitive recursive function that emulates a single step in its evolution: TSToPR[{n_, rule_}] := Fold[Apply[c, Flatten[{#1, Array[p, # 2], c[r[z, c[r[p[1], s], c[r[z, p[2]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]], p[#2]]}]] & , c[c[r[p[1], s], p[1], c[r[p[1], r[z, c[s, c[s, s]]]], c[c[r[z, c[r[p[1], s], c[r[z, c[s, z]], c[r[p[1], r[z, c[r[p[1], s], c[r[z, p[2]], c[ r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]]], p[2], p[3]]], p[1]]], p[1], p[1]], p[1]], p[2]]], p[n + 1], MapIndexed[c[r[z, c[r[p[1], p[4]], p[2], p[3], p[4]]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[Length[#2] + 1]], # 1 〚 1 〛 , #1 〚 2 〛 ] & , Nest[Partition[#1, 2] & , Table[Nest[c[s, #] & z, FromDigits[Reverse[IntegerDigits[i, 2, n] /. rule] + 1, 3]], {i, 0, 2 n - 1}], n - 1], {0, n - 1}]], Range[n, 1, -1]] (For tag system (a) from page 94 this yields a primitive recursive function of size 325.)

(Note that given explicit coordinates, one can check whether one is in d or more dimensions by asking for all possible points Det[Table[(x[i] - x[j]) .

The number of ways of writing an integer n as a sum of two primes can be calculated explicitly as Length[Select[n - Table[Prime[i], {i, PrimePi[n]}], PrimeQ]] .

Note first that the configuration of cells in the rows at the bottom of each picture can be thought of as successive finite approximations to tables for an oracle (see page 1126 ) which gives the solution to the halting problem for each possible input to the system.

An initial condition consisting of n white cells with one black cell in the middle can then be obtained with the function (see below for comments on this and other Mathematica functions) CenterList[n_Integer] := ReplacePart[Table[0, {n}], 1, Ceiling[n/2]] For cellular automata of the kind discussed in this chapter, the rule can also be represented by a list.

In analogy to digits in a concatenation sequence the terms in the sequence Flatten[Table[Rest[ContinuedFraction[a/b]], {b, 2, n}, {a, b - 1}]] are known to occur with the same frequencies as they would in the continued fraction representation for a randomly chosen number.

The undecidability of PCP can be seen to follow from the undecidability of the halting problem through the fact that the question of whether a tag system of the kind on page 93 with initial sequence s ever reaches a halting state (where none of its rules apply) is equivalent to the question of whether there is a way to satisfy the PCP constraint TSToPCP[{n_, rule_}, s_] := Map[Flatten[IntegerDigits[#, 2, 2]] &, Module[{f}, f[u_] := Flatten[Map[{1, #} &, 3u]]; Join[Map[{f[Last[#]], RotateLeft[f[First[#]]]} &, rule], {{f[s], {1}}}, Flatten[ Table[{{1, 2}, Append[RotateLeft[f[IntegerDigits[j, 2, i]]], 2]}, {i, 0, n - 1}, {j, 0, 2 i - 1}], 1]]], {2}] Any PCP constraint can also immediately be related to the evolution of a multiway tag system of the kind discussed in the note below.