And quite probably the same is true of many nerve cells involved in the general process of doing the analog of producing hash codes. … So how does this compare to what we know of actual human memory? … But there are also ones that we do not.

As a specific example consider taking a series of steps, and at each step picking a square in the array discussed above at random, then reversing the color of this square whenever doing so will not increase the total number of squares in the array that violate the constraints. … In practical situations this kind of approximate result can sometimes be useful, but the pictures at the top of the facing page show that the actual patterns obtained do not look much at all like the exact results that we saw for this system in Chapter 5 . … The procedure starts with a randomly chosen pattern, then at each step picks a square in the pattern at random, and reverses the color of this square whenever doing so does not increase the total number of squares in the pattern that violate the constraints.

Yet traditional mathematical models often in effect imply that systems in nature can do things like this. … And this has in the past often been taken to imply that systems in nature are able to do computations that are somehow fundamentally more sophisticated than standard computational systems. But for several reasons I do not believe this conclusion.

Yet for the majority of cases shown here there is at least no obvious way to do this. … So what does this mean for science? In the past it has normally been assumed that there is no ultimate limit on what science can be expected to do.

So what does all this mean about extraterrestrial intelligence? … For while this is undoubtedly very common say in cellular automata, the most immediate suggestions of it are in class 4 systems like rule 110 that in effect happen to do their computations in a way that looks at least somewhat similar to the way we as humans are used to doing them. … But if we require something that follows too many of the details of us as humans there is already evidence that it does not exist.

But among slightly larger clusters there turn out to be many that do not overlap themselves—and indeed this becomes common as soon as there are at least two connections between each dangling one. … Yet in our everyday experience space certainly does not seem to have this property. … Replacements for sets of clusters that do not overlap have the property of causal invariance.

And as the pictures on the facing page show, different Turing machines can take very different numbers of steps to do the computations they do. … But while this means that for a given input each of them yields the same output, the pictures demonstrate that they usually take a different number of steps to do so. … And it turns out that at least among 2-state 2-color Turing machines this is the only one that computes the function it computes—so that at least if one wants to use a program this simple there is no faster way to do the computation.

So how does the human visual system actually work? … Does our visual system also work by picking out specific features of these? Everyday experience suggests that indeed it does.

So what does all this mean for extraterrestrial intelligence? … Yet we do not believe that we have ever seen any such artifacts. But how do we know for sure?

Practical details make it somewhat difficult to do systematic experiments on such programs. But the experiments I have carried out do suggest that, just as with simple register machines, searching through many millions of short programs typically yields at least a few that exhibit complex and seemingly random behavior. … How can one set up a simple idealization of the transformations on symbolic expressions that Mathematica does?