Page 114 - 49A Field Guide to Genetic Programming

100 11 GP Theory and its Applications

0.1
0.01
0.001
0.0001
1e-05
1e-06
255
1e-07
201
0 127 151
10 20 Size
30 91
40 50 63
60 31
Three-Input Boolean equivalence class 70 80 1
Figure 11.1: Proportion of NAND trees that yield each three-input func-
tions. As circuit size increases the distribution approaches a limit.

e) CCNOT (Toffoli gate) computer, f) quantum computers, g) the “average”
computer and h) AND, NAND, OR, NOR expressions.
Recently, (Langdon and Poli, 2006; Poli and Langdon, 2006b) started ex-
tending 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, impor-
tant quantities, such as the halting probability and the run time of halting
programs. This showed a scaling law indicating that the halting probabil-
√
ity for programs of length L is of order 1/ L, while the expected number
√
of instructions executed by halting programs is of order L. In contrast
to many proposed Markov models, this can be done very efficiently, mak-
ing it possible to compute these quantities for programs of tens of million
instructions in a few minutes. Experimental results confirmed the theory.