W.B.Langdon . 11 May 2011 2006 papers , full list
ABSTRACT
Theoretical models of Turing complete linear genetic programming (GP) programs suggest the fraction of halting programs is vanishingly small. Convergence results proved for an idealised machine, are tested on a small computer with (finite) memory, conditional branches and jumps. Simulations confirm Turing complete fitness landscapes of this type hold at most a vanishingly small fraction of usable solutions.
On Turing complete T7 and MISC F-4 program fitness landscapes,
W. B. Langdon and R. Poli.
Technical report
CSM-445, ISSN 1744-8050, Dec 2005, Essex University.
Presented at Dagstuhl
PDF
ABSTRACT
We use the minimal instruction set F-4 computer to define a minimal Turing complete T7 computer suitable for genetic programming (GP) and amenable to theoretical analysis. Experimental runs and mathematical analysis of the T7, show the fraction of halting programs is drops to zero as bigger programs are run.