Evolutionary Turing Machines: The Quest for Busy Beavers

Evolutionary Turing Machines: The Quest for Busy Beavers

Penousal Machado (ISEC, Portugal), Francisco B. Pereira (ISEC, Portugal), Jorge Tavares (CISUC, Portugal), Ernesto Costa (CISUC, Portugal) and Amílcar Cardoso (CISUC, Portugal)
Copyright: © 2005 |Pages: 32
DOI: 10.4018/978-1-59140-312-8.ch002
OnDemand PDF Download:


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.

Complete Chapter List

Search this Book:
Table of Contents
Moshe Sipper
Leandro Nunes de Castro, Fernando J. Von Zuben
Chapter 1
Leandro Nunes de Castro, Fernando J. Von Zuben
Biologically inspired computing is just one of the branches of natural computing, which also encompasses artificial life, fractal geometry and... Sample PDF
From Biologically Inspired Computing to Natural Computing
Chapter 2
Penousal Machado, Francisco B. Pereira, Jorge Tavares, Ernesto Costa, Amílcar Cardoso
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... Sample PDF
Evolutionary Turing Machines: The Quest for Busy Beavers
Chapter 3
Fabiano Luis de Sousa, Fernando Manuel Ramos, Roberto Luiz Galski, Issamu Muraoka
In this chapter a recently proposed meta-heuristic devised to be used in complex optimization problems is presented. Called Generalized Extremal... Sample PDF
Generalized External Optimization: A New Meta-Heuristic Inspired by a Model of Natural Evolution
Chapter 4
Taro Yabuki, Hitoshi Iba
In this chapter, a new representation scheme for Genetic Programming (GP) is proposed. We need a Turing-complete representation for a general method... Sample PDF
Genetic Programming Using a Turing-Complete Representation: Recurrent Network Consisting of Trees
Chapter 5
Cândida Ferreira
In this chapter an artificial problem solver inspired in natural genotype/phenotype systems — gene expression programming — is presented. As an... Sample PDF
Gene Expression Programming and the Evolution of Computer Programs
Chapter 6
Vincenzo Cutello, Giuseppe Nicosia
The chapter describes the theory of clonal selection and its usage in designing and implementing immunological algorithms for problem solving and... Sample PDF
The Clonal Selection Principle for In Silico and In Vitro Computing
Chapter 7
Sergio Alonso, Oscar Cordon, Iñaki Fernández de Viana, Francisco Herrera
This chapter introduces two different ways to integrate Evolutionary Computation Components in Ant Colony Optimization (ACO) Meta-heuristic. First... Sample PDF
Integrating Evolutionary Computation Components in Ant Colony Optimization
Chapter 8
Gurdip Singh, Sanjoy Das, Shekhar V. Gosavi, Sandeep Pujar
This chapter introduces ant colony optimization as a method for computing minimum Steiner trees in graphs. Tree computation is achieved when... Sample PDF
Ant Colony Algorithms for Steiner Trees: An Application to Routing in Sensor Networks
Chapter 9
Vahid Sherafat, Leandro Nunes de Castro, Eduardo Raul Hruschka
Algorithms inspired by the collective behavior of social organisms, from insect colonies to human societies, promoted the emergence of a new field... Sample PDF
The Influence of Pheromone and Adaptive Vision in the Standard Ant Clustering Algorithm
Chapter 10
James Kennedy
Particle swarm optimization is a computer paradigm that is based on human social influence and cognition. Candidate problem solutions are randomly... Sample PDF
Particle Swarms: Optimization Based on Sociocognition
Chapter 11
Angelo Loula, Ricardo Gudwin, Sidarta Ribeiro, Ivan de Araujo, João Queiroz
Here we propose, based on the Peircean semiotics and informed by neuroethological constraints, a methodology to simulate the emergence of symbolic... Sample PDF
Synthetic Approach to Semiotic Artificial Creatures
Chapter 12
Jean-Philippe Rennard
This chapter introduces the twin deadlocks of strong artificial life. Conceptualization of life is a deadlock both because of the existence of a... Sample PDF
Perspectives for Strong Artificial Life
Chapter 13
Peter J. Bentley
Fractal proteins are a new evolvable method of mapping genotype to phenotype through a developmental process, where genes are expressed into... Sample PDF
Controlling Robots with Fractal Gene Regulatory Networks
Chapter 14
Mark Neal, Jon Timmis
The field of biologically inspired computing has generated many novel, interesting and useful computational systems. None of these systems alone is... Sample PDF
Once More Unto the Breach: Towards Artificial Homeostasis
Chapter 15
C. Ronald Kube, Chris A.C. Parker, Tao Wang, Hong Zhang
In this chapter, we review our recent research in the area of collective robotics, and the problem of controlling multiple robots in the completion... Sample PDF
Biologically Inspired Collective Robotics
Chapter 16
Thomas P. Trappenberg
In this chapter a brief review is given of computational systems that are motivated by information processing in the brain, an area that is often... Sample PDF
Continuous Attractor Neural Networks
About the Authors