Abstract
The computational potential of artificial living systems can be studied without knowing the algorithms that govern the behavior of such systems. What is needed is a formal model that neither overestimates nor underestimates their true computational power. Our basic model of a single organism will be the so-called cognitive automaton. It may be any device whose computational power is equivalent to a finite state automaton but which may work under a different scenario than standard automata. In the simplest case such a scenario involves a potentially infinite, unpredictable interaction of the model with an active or passive environment to which the model reacts by learning and adjusting its behaviour or even by purposefully modifying the environment in which it operates. One can also model the evolution of the respective systems caused by their architectural changes. An interesting example is offered by communities of cognitive automata. All the respective computational systems show the emergence of a computational power that is not present at the individual level. In all but trivial cases the resulting systems possess a super-Turing computing power. That is, the respective models cannot be simulated by a standard Turing machine and in principle they may solve non-computable tasks. The main tool for deriving the results is non-uniform computational complexity theory.
This research was partially supported by GA ČR grant No. 201/00/1489 and by EC Contract IST-1999-14186 (Project ALCOM-FT).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Balcázar, J. L.-Díaz, J.-Gabarró, J.: Structural Complexity I. Second Edition, Springer, 1995, 208 p.
Hodges, A.: Turing — A Natural Philosopher. Phoenix, 1997, 58 p.
Karp, R.M.-Lipton, R. J.: Some connections between non-uniform and uniform complexity classes, in Proc. 12th Annual ACM Symposium on the Theory of Computing (STOC’80), 1980, pp. 302–309.
Maass, W.-Bishop, C., editors: Pulsed Neural Networks. MIT-Press (Cambridge), 1998.
Orponen, P.: An overview of the computational power of recurrent neural networks. Proc. of the Finnish AI Conference (Espoo, Finland, August 2000), Vol. 3: ”AI of Tomorrow”, 89–96. Finnish AI Society, Vaasa, 2000.
Penrose, R.: The Emperor’s New Mind. Concerning Computers, Mind and the Laws of Physics. Oxford University Press, New York, 1989.
Šíma, J.-Wiedermann, J.: Theory of Neuromata. Journal of the ACM, Vol. 45, No. 1, 1998, pp. 155–178.
Turing, A. M.: On computable numbers, with an application to the Entscheidungs problem, Proc. London Math. Soc., 42-2 (1936) 230-265; A correction, ibid., 43 (1937), pp. 544–546.
Turing, A.M: Systems of logic based on ordinals, Proc. London Math. Soc. Series 2, 45 (1939), pp. 161–228.
Turing, A. M.: Computing machinery and intelligence, Mind 59 (1950) 433–460.
Valiant, L.G.: Circuits of the Mind. Oxford University Press, New York, Oxford, 1994, 237 p., ISBN 0-19-508936-X.
van Leeuwen, J.-Wiedermann, J.: On algorithms and interaction, in: M. Nielsen and B. Rovan (Eds), Mathematical Foundations of Computer Science 2000, 25th Int. Symposium (MFCS’2000), Lecture Notes in Computer Science Vol. 1893, Springer-Verlag, Berlin, 2000, pp. 99–112.
van Leeuwen, J.-Wiedermann, J.: The Turing machine paradigm in contemporary computing, in: B. Enquist and W. Schmidt (Eds), Mathematics Unlimited-2001 and Beyond, Springer-Verlag, 2001, pp. 1139–1155.
van Leeuwen, J.-Wiedermann, J: A computational Model of Interaction in Embedded Systems. Technical Report TR CS-02-2001, Dept. of Computer Science, University of Urecht, 2001
van Leeuwen, J,-Wiedermann, J.: Breaking the Turing Barrier: the Case of the Internet. Manuscript in preparation, February, 2001.
Wagner, K.-Wechsung, G.: Computational Complexity, VEB Deutscher Verlag der Wissenschaften, Berlin 1986, 551 p.
Wiedermann, J.: Toward Computational Models of the Brain: Getting Started. Neural Network World, Vol. 7, No. 1, 1997, pp. 89–120.
Wiedermann, J.: Towards Algorithmic Explanation of Mind Evolution and Functioning (Invited Talk). In: L. Brim, J. Gruska and J. Zlatuška (Eds.), Mathematical Foundations of Computer Science, Proc. of the 23-rd International Symposium (MFCS’98), Lecture Notes in Computer Science Vol. 1450, Springer Verlag, Berlin, 1998, pp. 152–166.
Wiedermann, J.: Simulated Cognition: A Gauntlet Thrown to Computer Science. ACM Computing Surveys, Vol. 31, Issue 3es, paper No. 16, 1999.
J. Wiedermann: Intelligence as a Large-Scale Learning Phenomenon. Technical Report ICS AV CR No. 792, 1999, 17 p.
Wiedermann, J.: The computational limits to the cognitive power of neuroidal tabula rasa, in: O. Watanabe and T. Yokomori (Eds.), Algorithmic Learning Theory, Proc. 10th International Conference (ALT’99), Lecture Notes in Artific. Intelligence, Vol. 1720, Springer Verlag, Berlin, 1999, pp. 63–76.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wiedermann, J., van Leeuwen, J. (2001). Emergence of a Super-Turing Computational Potential in Artificial Living Systems. In: Kelemen, J., Sosík, P. (eds) Advances in Artificial Life. ECAL 2001. Lecture Notes in Computer Science(), vol 2159. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44811-X_5
Download citation
DOI: https://doi.org/10.1007/3-540-44811-X_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42567-0
Online ISBN: 978-3-540-44811-2
eBook Packages: Springer Book Archive