Abstract
Since universal induction is a central topic in artificial general intelligence (AGI), it is argued that compressing all sequences up to a complexity threshold should be the main thrust of AGI research. A measure for partial progress in AGI is suggested along these lines. By exhaustively executing all two and three state Turing machines a benchmark for low-complexity universal induction is constructed. Given the resulting binary sequences, programs are induced by recursively constructing a network of functions. The construction is guided by a breadth-first search departing only from leaves of the lowest entropy programs, making the detection of low entropy (“short”) programs efficient. This way, all sequences (80% of the sequences) generated by two (three) state machines could be compressed back roughly to the size defined by their Kolmogorov complexity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
H-Prize, H.: http://prize.hutter1.net (accessed: May 17, 2015)
Cover, T.M., Thomas, J.A.: Elements of information theory. John Wiley & Sons (2012)
Friedlander, D., Franklin, S.: LIDA and a theory of mind. In: 2008: Proceedings of the First AGI Conference on Artificial General Intelligence, vol. 171, p. 137. IOS Press (2008)
Hernandez-Orallo, J.: Beyond the turing test. Journal of Logic, Language and Information 9(4), 447–466 (2000)
Hutter, M.: Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, 300 pages. Springer, Berlin (2005). http://www.hutter1.net/ai/uaibook.htm
Kitzelmann, E.: Inductive Programming: A Survey of Program Synthesis Techniques. In: Schmid, U., Kitzelmann, E., Plasmeijer, R. (eds.) AAIP 2009. LNCS, vol. 5812, pp. 50–73. Springer, Heidelberg (2010)
Kurzweil, R.: The singularity is near: When humans transcend biology. Penguin (2005)
Legg, S., Hutter, M.: A collection of definitions of intelligence. In: Goertzel, B., Wang, P. (eds.) Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms. Frontiers in Artificial Intelligence and Applications, vol. 157, pp. 17–24. IOS Press, Amsterdam (2007). http://arxiv.org/abs/0706.3639
Legg, S., Veness, J.: An Approximation of the Universal Intelligence Measure. In: Dowe, D.L. (ed.) Solomonoff Festschrift. LNCS, vol. 7070, pp. 236–249. Springer, Heidelberg (2013)
Levin, L.A.: Universal sequential search problems. Problemy Peredachi Informatsii 9(3), 115–116 (1973)
Li, M., Vitányi, P.M.: An introduction to Kolmogorov complexity and its applications. Springer (2009)
Looks, M., Goertzel, B.: Program representation for general intelligence. In: Proc. of AGI, vol. 9 (2009)
Mahoney, M.V.: Text compression as a test for artificial intelligence. In: AAAI/IAAI, p. 970 (1999)
Potapov, A., Rodionov, S.: Universal Induction with Varying Sets of Combinators. In: Kühnberger, K.-U., Rudolph, S., Wang, P. (eds.) AGI 2013. LNCS, vol. 7999, pp. 88–97. Springer, Heidelberg (2013)
Solomonoff, R.J.: A formal theory of inductive inference. Part I. Information and Control 7(1), 1–22 (1964)
Veness, J., Ng, K.S., Hutter, M., Uther, W., Silver, D.: A Monte-Carlo AIXI approximation. Journal of Artificial Intelligence Research 40(1), 95–142 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Franz, A. (2015). Toward Tractable Universal Induction Through Recursive Program Learning. In: Bieger, J., Goertzel, B., Potapov, A. (eds) Artificial General Intelligence. AGI 2015. Lecture Notes in Computer Science(), vol 9205. Springer, Cham. https://doi.org/10.1007/978-3-319-21365-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-21365-1_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21364-4
Online ISBN: 978-3-319-21365-1
eBook Packages: Computer ScienceComputer Science (R0)