www.gp-field-guide.org.uk
Contents Top Previous Next

11.2 Search Spaces

The characterisation of the space of computer programs explored by GP has been another main topic of theoretical research (Langdon and Poli2002). Of course results describing the space of all possible programs are widely applicable, not only to GP and other search-based automatic programming techniques, but also to many other areas ranging from software engineering to theoretical computer science.

In this category are theoretical results showing that the distribution of functionality of non Turing-complete programs approaches a limit as program length increases. That is, although the number of programs of a particular length grows exponentially with length, beyond a certain threshold the fraction of programs implementing any particular functionality is effectively constant. For example, in Figure  11.1 we plot the proportion of binary program trees composed of NAND gates which implement each of the 223 = 256 Boolean functions of three inputs.


PIC

Figure 11.1: Proportion of NAND trees that yield each three-input functions. As circuit size increases the distribution approaches a limit.


Notice how, as the length of programs increases, the proportion of programs implementing each function approaches a limit.

This does not happen by accident. There is a very substantial body of empirical evidence indicating that this happens in a variety of other systems. In fact, there are also mathematical proofs of these convergence results for two important forms of programs: Lisp (tree-like) S-expressions (without side effects) and machine code programs without loops (Langdon2002a,b2003a,b2005bLangdon and Poli2002). That the limiting distribution of functionality reaches a limit as program length increases was also proven for a variety of other non-Turing complete computers and languages, including: a) cyclic (increment, decrement and NOP), b) bit flip computer (flip bit and NOP), c) any non-reversible computer, d) any reversible computer, e) CCNOT (Toffoli gate) computer, f) quantum computers, g) the "average" computer and h) AND, NAND, OR, NOR expressions.

Recently, (Langdon and Poli2006Poli and Langdon2006b) started extending these results to Turing complete machine code programs. For this purpose, a simple, but realistic, Turing complete machine code language, T7, was considered. It includes: directly accessed bit addressable memory, an addition operator, an unconditional jump, a conditional branch and four copy instructions. A mathematical analysis of the halting process based on a Markov chain model of program execution and halting was performed. The model can be used to estimate, for any given program length, important quantities, such as the halting probability and the run time of halting programs. This showed a scaling law indicating that the halting probability for programs of length L is of order 1/rL-, while the expected number of instructions executed by halting programs is of order rL--. In contrast to many proposed Markov models, this can be done very efficiently, making it possible to compute these quantities for programs of tens of million instructions in a few minutes. Experimental results confirmed the theory.


www.gp-field-guide.org.uk
Contents Top Previous Next