Evolving Turing complete representations

Created by W.Langdon from gp-bibliography.bib Revision:1.4524

  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 =          "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.",

Genetic Programming entries for John R Woodward