Essay Abstract
Why is it so easy to generate complexity? Because essentially every non-trivial system is universal, that is, capable of exploring all complexity in its domain. In this sense there is Universality Everywhere. Automata, spin models and neural networks are the best understood examples of systems that jump to universality, and I also discuss some more speculative ones. One crucial consequence of universality is that it allows for self-reference and negation, which gives rise to paradoxes such as 'I am a liar'. The truth of this statement cannot be established -- it is undecidable. The liar paradox is at the core of the undecidability results in automata, provability theory, set theory, truth theory and epistemology. It is a very powerful paradox which cannot be fixed in a finite way. Undecidability is thus an inescapable consequence of the expressive power of the system, that is, of universality. In this sense, Universality Everywhere implies Undecidability Everywhere. I discuss some conceptual and practical implications of undecidability, as well as perspectives of overcoming these limitations. I also argue that universality is a statement about the power of simulation, that is, of how much a system can reach with the help of additional variables, and I discuss the relation of this notion of universality with emergence.
Author Bio
Gemma De las Cuevas is an Assistant Professor at the Institute for Theoretical Physics of the University of Innsbruck (Austria). Her research is centered around mathematical physics and quantum many-body physics. She is also interested in the universality and undecidability notions presented in this essay.