To understand this article, it is necessary to have a brief background in both cellular automata and genetic programs.

Conventional homogeneous cellular automata begin with a group of sites, each one of which has an identical structure of neighbors. Each site has some value, which is usually, though not necessarily, an integer often expressed in base 2. Thus a site might have the value 10001 represented in base 2 (17 in base 10). That value evolves according to some exogenously-imposed global rule that uses only the value of each site and some subset of that site's neighbors as its data. Traditionally, the subset of sites is the site itself and those within some distance (or radius) r of the site. The rule is the same for all the sites, hence the term "homogeneous cellular automata". [Note1]

In a cellular automaton, the value of all sites evolves synchronously. A ring in which each site has one neighbor on its left and one neighbor on its right, in which the value of each site can be 0 or 1, and in which the new value of the site is equal to the mod 2 sum of the site and these neighbors is a conventional cellular automaton. Figure 1 below illustrates such a cellular automaton with twelve sites on the ring through ten iterations. Position 1 appears at "1 o'clock" and position 12 appears at "12 o'clock". Iterations 1-5 appear left to right in the top row. Iterations 6-10 appear left to right in the second row. [Note2]

The evolution can be viewed in an alternative way by (1) coloring sites whose value is 1 as white and coloring sites whose value is 0 as black, (2) "snipping" each of the rings at some arbitrary point (such as between 12 o'clock and 1 o'clock), (3) displaying each of the snipped rings as a colored horizontal line whose beginning and end we know to be connected, and (4) putting lines representing later stages of evolution below those representing earlier stages of evolution. The evolution shown in Figure 1 can also be displayed as in Figure 2.

The rule used to evolve an automaton can be given an integer representation in a way pioneered by Wolfram [8]. The rule discussed above, in which the new value is the mod 2 sum of the site and its left and right neighbors, creates the following map between the neighborhood of a site and the new value at that site. [Note3]

If we now go down the right-most element of each line of the above table, we see 10010110. That sequence is a representation of the rule employed to evolve the automaton. We can think of this sequence as the binary number , which has a decimal equivalent of 150. The rule described above is thus often given the shorthand of "Rule 150". How many distinct rules can there be? Since it takes eight binary digits to represent a rule, there are 256 distinct possible rules. Generally, if the rule requires examination of x digits represented in base b and outputs a digit in base b, it takes digits in base b to represent the rule and there are thus possible rules. When b or x is large, this number can become amazingly large.

Inhomogeneous cellular automata also exist, in which each site evolves according to its own rule [9]. The site at the "first" position in an automaton might evolve according to Rule 150, whereas the site at the second position might evolve according to Rule 129, and the site in the third position might evolve according to Rule 226, and so forth. Figure 2 illustrates the evolution of such an inhomogeneous cellular automaton in which the initial state of the automaton is the same as the initial state of the automaton shown in Figure 1, but in which the sites respectively employ {150,129,226,14,154,158,141} as the rules for evolution.

One may think of this process as evolving behavior based on the individual site's prespecified mechanism for updating itself [10]. The sites thus react in their own ways to the behavior around them, but do not evolve in the ways in which they react to that behavior.

An inhomogeneous cellular automaton, however, can be recharacterized as a homogeneous cellular automaton. In the example above, the value at each site can be considered as a nine digit binary number, the first digit of which represents what we formerly called the value of the site and the last eight digits of which represents what we called the rule for evolving that site. Where a site has value 1 and uses Rule 150 () to update itself, the equivalent homogeneous cellular automaton has a value of 406 or . Generally, the value of a site is recharacterized as a now indistinguishable combination of what we formerly called the value of the site and the rule for updating that site. What one might call the data and the program have been merged into pure data.

In this homogeneous recharacterization of an inhomogeneous cellular automaton, the first digit of a site can vary, while the last eight digits (the rule part) cannot. To evolve, each site consults the first digit of the site to the left, all of its own nine digits, and the first digit of the site to the right. There is then a global rule--a sort of metaprogram--which itself can be characterized as a 2048 binary digit number that sets forth how the first digit of each new site is to be updated. In our example, the value of that rule in decimal form is about .

Generally, if each site in an inhomogeneous cellular automaton can take on k values and updates itself by looking at itself and sites within some radius r, it takes base k digits to specify an update rule and thus takes digits to specify the global update rule of the equivalent homogeneous cellular automaton. Obviously, for each homogeneous cellular automaton, there is an equivalent inhomogeneous automaton, with all the cells using the same update rule.

One can take the notion of inhomogeneity to the next level as well. Each site cannot only have a value and a rule for updating itself, but it can also have a rule for updating the rule by which it then updates itself. The site evolves its behavior based on the behavior of the neighboring sites, but does so in a way that itself evolves. The site thus exhibits what might be called learning. At any given time in our sample automaton, each site would have a one-digit value and an eight-digit update rule code. It would also have a fixed and very lengthy code for updating the update code based on the values at the neighboring sites and their update codes. Indeed, it appears that a complete specification of the code for updating the update code would take (about one billion) binary digits. [Note4]

The resulting inhomogeneous cellular automaton can, like all cellular automata, be converted into a homogeneous cellular automaton, but one with an almost inconceivably long global update rule.

Of course, at a theoretical level, there is no need to stop at second-level inhomogeneity. We might want the site to learn how to learn by updating the code by which it updates its update code. Each site would first examine the digits of itself and its three neighbors, and use an update rule with digits (this is 2 to about the three trillionth power) to update the digit update code used for updating the update rules used for revising the values. With the rules for updating the update codes in place, the automaton would then update the update codes. And with the update codes in place, the automaton would then update the values.

In mathematical theory, this process of recursion can continue indefinitely, with the lengths of the various update codes surpassing imagination. As a practical matter, however, no imaginable computer can handle this sort of data--we are well past the number of known particles in the universe--in any imaginable time. Hence, modeling learning and learning how to learn needs to employ a different mechanism than simply a raw specification of update codes. [Note5]

Genetic programs are a form of computer programs that evolve. The programs themselves have a structure in which the permissible arguments to each function are determined by a specified "grammar". Certain of the programs may "mate" with each other by permitting certain portions of one program to replace portions of another program. The points at which the mating programs "cross over" are determined by a "mating template". The programs may also mutate spontaneously.

A set of notebooks developed by Jacob permits Mathematica to generate random expressions from a particular grammatical structure. The user creates this grammatical structure by writing a list of correct expression patterns (templates) that are themselves Mathematica expressions. The process may be easier to demonstrate than describe. Code Fragment 1 shows an example.

A sentence consists of either a noun followed by a verb phrase followed by a noun, a noun followed by a verb phrase, or a sentence followed by a sentence followed by another sentence. A noun might in turn consist of an article followed by a thing. A verb phrase might consist of either a verb followed by an adverb or just a verb. A verb might be hit, examine, eat, or smell. A thing might be boy, gorilla, plant, cat, or girl. An adverb might be quickly, softly, really, or violently.

If we evaluate a notebook created by Jacob called GP-ExprGeneration.nb, the user may then input this grammar as an argument to one of several functions such as createExpression that then generate grammatically correct expressions at the desired level of complexity. Code Fragment 2 illustrates the process, creating a list of three sentences.

We can reformat this output to make it a bit more readable.

While these sentences may not make a great deal of sense, they represent permissible grammatical constructions.

The Jacob method for generating random symbolic expressions can also be used to generate structures with more apparent mathematical meaning. Code Fragment 3 is a minimal grammar of expressions that look a lot like Mathematica expressions.

In Code Fragment 4 we show how to create five random expressions using this grammar and the createExpression function.

Here are some sample results.

These expressions can be visualized as trees.

In a process analogous to mating in the "real world", expressions created in this grammar can be mated to each other by permitting any permissible component of the grammar in one expression to be replaced by any component of the mate that matches another (possibly different) component of the grammar. The computer code is treated analogously to biological material capable of evolution. Essentially, we snip off fragments from one expression that match a pattern and graft on fragments from a second expression that match a second (possibly different) pattern. If more than one fragment on each tree matches, we select randomly from the potential snip and graft candidates. The Mathematica code for this procedure of recombination is shown below in Code Fragment 6.

For example, we can mate the third expression in mathexpressions to the fourth expression in mathexpressions allowing any subexpression with a head of Integer in the first expression to be replaced by any subexpression with a head of Times in the second expression. We do this six times to illustrate the different possible results. [Note6]

We can then evaluate these expressions using some substitution rules in conjunction with the ReplaceRepeated construct.

A more general method of defining an extended set of genetic operators on symbolic expressions, such as recombination, inversion, deletion, duplication, and mutation, is described in detail in [7]. Further code examples are available at www.cpsc.ucalgary.ca/~jacob/IEC.

While inhomogeneous cellular automata can in theory be used to model agents that learn and that learn how to learn, as noted above, there is a practical impediment: the amount of data needed to characterize the rules for learning exceeds the size of any conceivable computer, even for relatively simple automata. One way around this is to permit a site to hold both data and a computer program for updating itself. The computer program references itself and the data surrounding it to figure out how to update the site. If the set of operations in the computer program is broad enough, this method should be capable of spanning a broad set of the possible rules for learning and learning how to learn. One way to create a rich set of operations is through genetic programs.