Using Genetic Programming for Turing Machine Induction
Turing machines are playing an increasingly significant role in Computer Science domains such as bioinformatics. Instead of directly formulating a solution to a problem, a Turing machine which produces a solution algorithm is generated. The original probl
- PDF / 234,966 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 118 Downloads / 258 Views
School of Computer Science, Univesity of KwaZulu-Natal, Westville Campus, Westville, KwaZulu-Natal, South Africa [email protected] 2 School of Computer Science, University of KwaZulu-Natal, Pietermaritzburg Campus, Pietermartizburg, KwaZulu-Natal, South Africa [email protected]
Abstract. Turing machines are playing an increasingly significant role in Computer Science domains such as bioinformatics. Instead of directly formulating a solution to a problem, a Turing machine which produces a solution algorithm is generated. The original problem is reduced to that of inducing an acceptor for a recursively enumerable language or a Turing machine transducer. This paper reports on a genetic programming system implemented to evolve Turing machine acceptors and transducers. Each element of the population is represented as a directed graph and graph crossover, mutation and reproduction are used to evolve each generation. The paper also presents a set of five acceptor and five transducer benchmark problems which can be used to test and compare different methodologies for generating Turing machines. The genetic programming system implemented evolved general solutions for all ten problems. Keywords: Turing machines, genetic programming, grammatical inference.
1 Introduction As the potential of Turing machines in more recent domains of Computer Science such as bioinformatics is being realized, interest in the automatic induction of these automata is growing. While there has been a number of investigations into the evolution of other forms of automata such as finite acceptors ([2] and [4]) and transducers ([3] and [6]), there has not been much research into the use of evolutionary algorithms for Turing machine induction. Research in this domain was initiated by the study conducted by Tanomaru [7] in the early nineties. The main motivation of Tanomaru’s study was that once a Turing machine is evolved it can be easily implemented as a computer program solution to the problem. Tanomaru used an evolutionary algorithm to generate Turing machine transducers for two problems. This system did not scale well when applied to Turing machine acceptor problems and “population shifting” was introduced to overcome this problem. The revised system evolved solutions to three acceptor problems. Since this initial study there has not been much research into this domain. In the late nineties Pereria et al. [5] have evolved solutions to the Busy Beaver problem. The main aim of this study was to test the effectiveness of using graph-crossover instead of M. O’Neill et al. (Eds.): EuroGP 2008, LNCS 4971, pp. 350–361, 2008. © Springer-Verlag Berlin Heidelberg 2008
Using Genetic Programming for Turing Machine Induction
351
two-point crossover. Graph-crossover was found to improve the success rate of the evolutionary algorithm and the system produced some of the best results in this field. In 2001 Vallejo et al. [8] implemented an evolutionary algorithm to induce Turing machine acceptors for recognizing HIV biosequences. The biosequence
Data Loading...
