Impact of Loops and Memory on GP Fitness Landscapes

W. B. Langdon
Computer Science
University of Essex Logo

Paper presented at EuroGP-2006 pages 225-237 details


GP is evolving O(1) functions

T7 Minimal Turing Complete CPU

T7 Architecture

Architecture of T7 and example random program


Controlling Run Away Programs

Almost all T7 Programs Loop

T7 looping and non-looping Programs

Model of Random Programs

A Program Segment - Random code ending with a random jump

sequential code followed by random jump

Forming Loops:Segments model

Probability of Halting

Proportion of Programs without loops falls as 1/sqrt(length)

Terminating T7 Programs
Segments model over, but gives 1/√x scaling.
Approx 1% not proved to loop forever

Number of Halting Programs rises exponentially with length

Number of Terminating T7 Programs The number of halting T7 programs containing 16 million instructions exceeds 10100 000 000.

Average Run Time (non-looping)

Run time on Terminating Programs

Run time of T7 Terminating Programs

Run time of non-looping programs fits Markov prediction.
Mean run time of all terminating programs length¾
Assuming maximum run time is limited by small, 12 bytes, memory becoming non-random.

Suppose we have a GHz T7 computer

Conclusions 1

The answer to the halting problem is No