Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


[Methods of] encoding sequences by integers

In many constructions it is useful to be able to encode a list of integers of any length by a single integer. (See e.g. page 1127.) One way to do this is by using the Gödel number Product[Prime[i]^list[[i]],{i,Length[list]}]. An alternative is to use the Chinese Remainder Theorem. Given p=Array[Prime, Length[list], PrimePi[Max[list]]+1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive)

CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]]

yields a number x such that Mod[x, p] == list. Based on this

LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[#1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]]

will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function

Mod[x, Prime[ Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]] == 0 &] &, 0, n]]]]

From Stephen Wolfram: A New Kind of Science [citation]