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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming – An Introduction – On the Automatic Evolution of Computer Programs and its Applications. Morgan Kaufmann Publishers, Inc., San Francisco (1998)
Lucas, S.M., Reynolds, T.: Learning DFA: Evolution versus Evidence Driven State Merging. In: The Proceedings of the 2003 Congress on Evolutionary Computation (CEC 2003), pp. 351–358. IEEE Press, Los Alamitos (2003)
Lucas, S.M.: Evolving Finite State Transducers: Some Initial Explorations. In: Ryan, C., Soule, T., Keijzer, M., Tsang, E.P.K., Poli, R., Costa, E. (eds.) EuroGP 2003. LNCS, vol. 2610, pp. 130–141. Springer, Heidelberg (2003)
Luke, S., Hamahashi, S., Kitano, H.: Genetic Programming. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzan, M.H., Honavar, V., Jakiela, M., Smith, R.E. (eds.) Proceedings of the Genetic Programming and Evolutionary Computation Conference, Orlando, Florida, USA, vol. 2, pp. 1098–1105 (1999)
Pereria, F.B., Machado, P., Costa, E., Cardoso, A.: A Graph Based Crossover – A Case Study with the Busy Beaver Problem. In: Banzhaf, W., Daida, J. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2, pp. 1149–1155. Morgan Kaufmann, San Francisco (1999)
Naidoo, A., Pillay, N.: The Induction of Finite Transducers Using Genetic Programming. In: Ebner, M., O’Neill, M., Ekárt, A., Vanneschi, L., Esparcia-Alcázar, A.I. (eds.) EuroGP 2007. LNCS, vol. 4445, pp. 371–380. Springer, Heidelberg (2007)
Tanomaru, J.: Evolving Turing Machines. In: Hao, J.K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 167–180. Springer, Heidelberg (1993)
Vallejo, E.E., Ramos, F.: Evolving Turing Machines for Biosequence Recognition and Analysis. In: Miller, J.R., Tomassini, M., Lanzi, P.L., Ryan, C., Tettamanzi, A.G.B. (eds.) EuroGP 2001. LNCS, vol. 2038, pp. 192–203. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Naidoo, A., Pillay, N. (2008). Using Genetic Programming for Turing Machine Induction. In: O’Neill, M., et al. Genetic Programming. EuroGP 2008. Lecture Notes in Computer Science, vol 4971. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78671-9_30
Download citation
DOI: https://doi.org/10.1007/978-3-540-78671-9_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78670-2
Online ISBN: 978-3-540-78671-9
eBook Packages: Computer ScienceComputer Science (R0)