Chapter 4: Systems Based on Numbers

Section 1: The Notion of Numbers

Gray code

In looking at digit sequences, it is sometimes useful to consider ordering numbers by a criterion other than their size. An example is Gray code ordering, in which successive numbers are arranged to differ in only one digit. 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. (Note that the digit sequence picture is turned on its side relative to those in the main text). The number which appears at position i is given by BitXor[i,Floor[i/2]]. (Iterating the related function BitXor[i,2i] yields numbers whose digit sequences correspond to the rule 60 cellular automaton).

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