Abstract
In this chapter we study the feasibility of using
Turing Machines as a model for the evolution of
computer programs. To assess this idea we select, as
test problem, the Busy Beaver - a well-known
theoretical problem of undisputed interest and
difficulty proposed by Tibor Rado in 1962. We focus our
research on representational issues and on the
development of specific genetic operators, proposing
alternative ways of encoding and manipulating Turing
Machines. The results attained on a comprehensive set
of experiments show that the proposed techniques bring
significant performance improvements. Moreover, the use
of a graph based crossover operator, in conjunction
with new representation techniques, allowed us to
establish new best candidates for the 6, 7, and 8
states instances of the 4 tuple Busy Beaver problem.
Users
Please
log in to take part in the discussion (add own reviews or comments).