The system depicted in the XKCD comic is based on cellular automaton rule 110, which has been proven "universal" aka Turing-complete. (Cellular automaton rule 34 has uninteresting behavior.)
A cellular automaton, though, updates all cells simultaneously, while our stick figure is going one cell at a time. So the system as "implemented" is more like a simple Turing machine that executes the equivalent of rule 110 as its head scans back and forth along the tape. Such a Turing machine is easily constructed (see NKS page 665 for examples for two other cellular automaton rules).
Leaving the pattern behind (that is, creating a new row with each pass instead of just modifying a single row over and over again) is unnecessary for the computation. Given that the desert has sufficient dimensions to allow for it, I suppose there's no reason not to, but the continued existence of those earlier rows doesn't affect anything or mean anything. It would work just as well if he were limited to one row in an infinite hallway or, perhaps, moving hats between the upper and lower pegs of an infinitely long hat rack. (Moving the rocks on the ground requires so much bending over...)
If the computation using rocks in the desert includes generating conscious beings, then the ongoing computation is the substrate (probably the deepest of multiple layers of computational substrate) for that consciousness. The pattern left behind, by contrast, is just a big bitmap of dumb rocks.
That the pattern is not the same as the process, can be obscured by mistakenly assuming equivalences that apply in mathematics but not in computing.
In mathematics, the expression "2^10" is generally regarded as completely equivalent to the expression "1024." Nothing mathematical is actually gained or learned by doing the multiplication, or by any deterministic computation. For instance, generating a detailed image of a portion of a zoomed in Mandelbrot Set does not create or reveal anything that wasn't already implicit in the equations that define the set.
But computing isn't mathematics. Computing isn't anything until it happens. You don't have 1024 from 2^10 until you multiply it out. You don't actually know what the Mandelbrot set looks like until you do the computing to generate the image.
Mathematical proofs about computing can be created without actually doing the computations described in the proofs, but that's mathematics not computing. On the other hand, the computing required in the course of doing mathematics must be done in order to count. Proofs, for instance, must actually be found and enumerated -- that's a form of computation -- and not merely claimed to exist implicitly in the axioms of a system.
The close relationship between mathematics and computing generates understandable confusion. But implicit-ness applies only in mathematics. In mathematics the ten billionth digit of pi exists implicitly; in computing it exists when you've done the work to figure out what it is. Minesweeper as the title of a piece of software is implicit in the patterns of bits on my hard drive when my computer is off, but Minesweeper as an actual game event doesn't happen unless the program is running.
So if consciousness is a phenomenon of computation, it does not follow that a string of symbols specifying a computation can be conscious. That attempted reductio ad absurdum fails. That something can become conscious does not imply that it is conscious, any more than than a tree is a chest of drawers because under the right circumstances it can become a chest of drawers.
Perhaps the pattern of a meteor shower or the expansion of pi can generate strings of digits which could generate consciousness if used as the input of a suitable computation. That doesn't mean anything unless that computation actually happens. If it does not happen, then there is no consciousness.
And the proposition that "everything is computation, so therefore every possible computation must occur" cannot rescue the notion. Not only does the conclusion not follow from the premise, but the premise itself at best (that is, if it's even true) equivocates the meaning of "computation." Not all computation is universal, and universality is a rather low bar to set if we want to specify computation that is capable of interesting and complex phenomena such as consciousness. At present only certain systems have been proved capable of universal computation. Generally, all such systems, despite their enormous diversity, have certain characteristics in common. Most notably, persistent but changeable local state information.
Some systems (Wolfram calls them Class 1) do not preserve any state information. A puff of smoke just dissipates and disappears, reaching the same end state regardless of the initial shape of the puff. Some systems (Wolfram calls them Class 2) preserve state information but do not permit them to change, except perhaps in a repeating pattern that doesn't compute anything new. That's your rock. Some systems (Wolfram calls them Class 3) internally propagate state information indiscriminately so that the state of any part quickly (at some internal propagation speed) affects the state of all other parts, with no possibility of preserving information for the time it takes to access it. These systems generate randomness. That's your bowl of soup.
All known universal computers are Class 4, for which internal information propagation is locally contingent on state. Turing machines have a tape that remains unchanged except for the location where the head currently is; Class 4 cellular automata have fixed or moving local structures that persist until they interact with other local structures they come in contact with; conventional computers have memory and registers; neural networks have synapse weightings; genetic systems have populations of genomes; formal systems have strings of symbols and rules governing which parts of a string can be changed at any given point.
(Wolfram proposes that Class 3 systems are also capable of universal computation. I think he's wrong about that.)
So, where do you look for the consciousness that we're pretty sure does exist, in our own selves? Somewhere in the brain, but where? In the ion channels? In the map of neural connections or the matrix of their coefficients? That's like looking for the heat in the pixels of a digital photo of a forest fire. It's in the computation. Or it isn't anywhere.
Respectfully,
Myriad
