- author = "John Woodward",
- title = "Evolving {Turing} complete representations",
- booktitle = "Proceedings of the 2003 Congress on Evolutionary Computation CEC2003",
- editor = "Ruhul Sarker and Robert Reynolds and Hussein Abbass and Kay Chen Tan and Bob McKay and Daryl Essam and Tom Gedeon",
- pages = "830--837",
- year = "2003",
- publisher = "IEEE Press",
- address = "Canberra",
- publisher_address = "445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331, USA",
- month = "8-12 " # dec,
- organisation = "IEEE Neural Network Council (NNC), Engineers Australia (IEAust), Evolutionary Programming Society (EPS), Institution of Electrical Engineers (IEE)",
- keywords = "genetic algorithms, genetic programming, Automatic testing, Biological information theory, Code standards, Computational modelling, Computer science, Genetic mutations, History, Ice, Space exploration, Turing machines, complete computer programs, Turing Complete representations, crossover operator, halting problem, module boundaries, self terminating programs",
- ISBN = "0-7803-7804-0",
-
URL = "
http://www.cs.bham.ac.uk/~jrw/publications/2003/EvolvingTuringCompleteRepresentations/cec032e.pdf",
-
DOI = "
10.1109/CEC.2003.1299753",
-
abstract = "Standard GP, chiefly concerned with evolving functions
which are mappings from inputs to output, is not Turing
Complete. This paper raises issues resulting from
attempts at extending standard GP to Turing Complete
representations. Firstly, there is a problem when a
contiguous piece of code is moved to a new location (in
a different program) by crossover. In general its
functionality will be altered if global memory is used,
as other parts of the program may access the same piece
of memory. Secondly, traditional crossover does not
respect modules. Crossover can disrupt a group of
instructions that were working together (e.g. in the
body of a loop) in one parent, but end up separated in
two different offspring after reproduction.
A crossover operator is proposed that only operates at the boundaries of modules. The identification of module boundaries is made easy by using a representation in which explicit modules are defined, in contrast with other representations where the module boundaries would have to be identified by some other means.
The halting problem is a central issue, however as a consequence of this crossover operator we are more likely to produce self terminating programs, thus saving time when testing.",
- notes = "CEC 2003 - A joint meeting of the IEEE, the IEAust, the EPS, and the IEE.",
