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.

Download Essay PDF File

Dear Gemma De las Cuevas,

"The liar paradox is at the core of the undecidability results in automata, provability theory, set theory, truth theory and epistemology."

If the above assertion is at the heart of undecidability, the problem can be easily solved. Take for instance: 'All Cretes are liars said the Crete', which is a problem only in formal logic, i.e. when the Crete is considered an element of the set of Cretes. The Cretes as a people, however, belong to a different category than individual Cretes. So, the liar paradox speaks of a trait of the people of Crete expressed by an individual Crete, which is perfectly fine. In Tarski's words: the individual Crete speaks in meta-language about an object-language concerning the traits of the people of Crete. The same holds for "This sentence is false" or "I'm lying". In all those examples categorically separated instances play a role (which logicians and computers can not deal with for principled reasons).

The 'undecidability' illness was basically cured

a) by Gödel's (1931) incompleteness theorem, which states that Logic has no domain of applicability other than itself

b) by Tarski's (1935) theory of truth, which states that no object-language can discuss it's truths.

Some illnesses though seem to be fairly attractive...

Heinz

    Dear Gemma,

    I enjoyed your essay tremendously, for not only is well-written and your thesis crystal clear, but I think that it brings forward some deep insights too. In particular, I never thought of universality (as power of simulation) in terms of additional variables. Indeed, it makes a nice connection with my (and Gisin's) proposal, and it would be nice to explore this further.

    I found insightful your analysis of (a certain class) of paradoxex as arising from the self-reference problem and negation. And how this issues is implied by universality, in your words: "since a universal system can be fed the description of any other system, it can also be fed its own description".

    I also have two naive questions:

    1) The whole starting point of your argument, namely the jump to universality, relies on the concept of complexity, which, however, I don't think it is defined in your essay besides an intuitive level (which perhaps is enough!). I was wondering if the universality claim is based on some particula, formal notion of complexity. And since you "define universailty as the ability to explore all complexity in a given domain", is complexity bounded from above?

    2) You mention Wolfram's Principle of Computational Equivalence ("all processes which are not obviously simple can be viewed as computations of equivalent

    sophistication"). Do you have any intutions on how this is justified?

    I wish you the best of luck for the contest!

    Cheers,

    Flavio

      Dear Flavio,

      Thanks a lot for reading the essay and for your feedback. I am very glad we found some points in common and would very much like to explore them.

      Regarding your questions:

      1) A priori I don't think one can characterise the jump to universality in terms of some complexity measure, since complexity measures are defined for specific fields (for formal languages, spin models, ....). What we understand is that universality happens when a system is expressive enough to interpret the description of any other system. Generally it does not take much "complexity" (in a loose sense) to do this, from which feature (i) of the jump to universality follows.

      What I think is possible, and should be done, is to establish rigorous ties between the jumps to universality in automata, spin models and neural networks, and other fields perhaps in the future, too. This means, for example, proving that if a spin model is universal then the automaton associated to it is universal in the Turing sense. (We have taken the first steps in this direction). These theorems will put different objects (automata, spin models, neural networks...) at the same level, and will rigorously compare their universality notions. Once this is established, we may be able to rigorously compare complexity notions among the different fields, too.

      Regarding your second question "you define universality as the ability to explore all complexity in a given domain, is complexity bounded from above?" No - that's why universality puts systems at the beginning of infinity. That's the beauty of it. I encourage you and everyone to read David Deutsch's book - it's truly wonderful and inspiring.

      2) Wolfram's book is, in my opinion, rather awkward. On the one hand, he presents an impressive range of experiments with cellular automata and many variations thereof (tag systems, register machines, substitution systems, ...) where he reproduces many interesting phenomena in fundamental physics, biology, perception... From this perspective, the book is very impressive. On the other hand, he makes claims which are not proven - they are only supported by his experiments. In fact, he does not even attempt to formalise these claims as conjectures, or as more precise statements which could be proven. This is the case for the Principle of Computational Equivalence. Moreover, he seems to ignore all existing literature, such as the very existence of universal Turing machines and the Church-Turing thesis.

      Thank you, Flavio, for these interesting questions, and I hope we see each other soon to talk about all of this.

      Best,

      Gemma

      Dear Heinz,

      Thank you for reading the essay and for your feedback.

      As I understand, the solution you are proposing to the liar paradox is an example of (the first step in the construction) of a hierarchy to solve the paradox. Namely, you suggest that Cretes as people belong to a different category to individual Cretes, thereby establishing "two levels" which avoid self-reference. With these two levels, one can devise a new liar paradox (which will sound involved). Building hierarchies to escape the paradox is indeed the commonly adopted solution, as mentioned in my essay.

      Regarding your two final comments, I am not exactly sure with what you mean in 1). Regarding 2) I agree that Tarski's theory of truth is a way of circumventing the paradox, but I don't think I agree with the statement that this cures the illness - for one reason, it is not a finite solution. (I recommend reading T. Bolander's entry on Self-reference in the Stanford Encyclopedia of Philosophy to learn about approaches to solve the liar paradox).

      Thanks for your input again!

      Best,

      Gemma

      Dear Gemma,

      thanks for your reply, there seems to be some common ground...

      As regards a) another way to express it is the generally accepted claim that logic has not solved its GROUNDING problem. When logic demands to be universally applicable (to any problem) it is equivalent to saying that it has no domain of applicability.

      In my FQXI essays as of 2015 I have argued that legitimate domains, hierarchies or whatever one wants to call these categories are separated by orthogonality and thus rest on Absolut non-contradiction and hence imply nescience. That means, every legitimate object-language is not as per Tarski member of the meta-language, but categorically separated from it. The trouble with logic is in its very positivity (affirmativity)! Whatever we say can not be better as 'not-false' in the context of natural- and legitimate object-languages. That is, the optimum way to speak about the world is the metaphor.

      Heinz

      Dear Heinz,

      Thanks a lot for your reply. This sounds very interesting. I specially liked your comment about the metaphor :) I will read carefully your essay from 2015 and get back to you.

      Thanks again,

      Gemma

      6 days later

      Dear Gemma,

      thanks for a highly readable and insightful essay! I love the phrase 'the long reach of undecidability'; it is perfectly evocative of the often subtle ways in which the phenomenon of undecidability is relevant to often seemingly quite remote areas, such as determining whether a certain Hamiltonian has an energy gap in the ground state.

      You present a few first steps towards a kind of meta-theoretic notion of universality, where the specific universalities of automata, spin systems, neural networks, and the like can be seen as examples of the same underlying phenomenon. I think that's a highly promising direction of research. To my mind, the first result in this area was obtained already by F. W. Lawvere in his famous fixed-point theorem, which unifies the various 'diagonalization'-arguments you note, such as Gödel's, Tarski's, Russell's, Turing's, and so on (see in particular Noson Yanofsky's excellent exposition on the subject).

      If that's the case, then perhaps the unifying features of the various notions of universality can be found in the conditions of applicability of Lawvere's theorem---which are, essentially, the requirements for a category to be Cartesian closed. Using this formalism, one might then strive to formulate a precise notion of universality applicable across those at first unrelated domains. (By means of some self-promotion, if I may, I have argued that this result also applies in a physical context, leading to many of the familiar phenomena of quantum mechanics.)

      I think there are also further domains with notions of universality that might fall into that fold. For instance, von Neumann proposed, by explicit analogy with the universal Turing machine, the notion of the universal constructor: a device which, given the requisite raw materials and an appropriate blueprint, can construct everything at all constructible within that domain. In contrast to the Turing machine, which operates on symbols, the domain on which the constructor acts, and within which it exists itself, are the same---thus, one can use this to study, e. g., self-reproduction, as the constructor itself is within the set of outputs of a constructor.

      Another example would be within formal systems, where statements can be encoded by means of Gödel numberings within, say, arithmetic---which of course leads to the most famous manifestation of undecidability, namely, Gödelian incompleteness. Similarly, perhaps, for language one might look at Noam Chomsky's merge-operator.

      I also think it's highly interesting to study how, exactly, the 'jump to universality' occurs. This seems to be a paradigm example of 'more is different': you pile on just an insignificant bit of extra complexity, and you essentially get everything there is, in an utter explosion of capacity. Trivial systems become capable of instantiating the most highly complex behaviors. This, to me, always seems like the closest to strong emergence anybody has ever gotten, and I wonder if it's possible to formulate a general theory of how this jump occurs, or what, exactly, is it that makes a universal system 'universal'.

      Anyway, thanks again for a highly intriguing and stimulating essay, and best of luck in the contest!

      Cheers

      Jochen

        Dear Jochen,

        Thank you so much for your comments! I believe they are very useful and will help me formalise some of the ideas of the essay - on universality, the jump to universality, and their application to various domains. I will keep you posted if I do any progress in these fronts :) Let's stay in touch.

        Thanks again, really.

        All the best,

        Gemma

        Dear Gemma De las Cuevas

        When I read the essays of young scientists a look at reference to see whether they are on the right track. To be on the right track, you need to penetrate the minds of the greats of science of the past who have unrivaled achievements (Newton, Boskovic, Maxwell,..., Planck, Einstein, Euler, Ramanujan). Everything else leads to paradoxes, singularities... and a waste of time.

        Regarda,

        Branko

          Dear Branko,

          Thanks for your comment, but I disagree. I don't think it's a waste of time not to cite very influential thinkers - I believe it can even be liberating :)

          Sincerely,

          Gemma

          Hi Gemma!

          This was a very fun read! I really love your point "Undecidability is thus an inescapable consequence of the expressive power of a system -- it is the other side of the coin of universality. Universality Everywhere, thus, implies Undecidability Everywhere." This is a very good point. but also, it seems that physical systems like biology don't seem to mind.

          It's interesting to think that we, as humans, can hold these paradoxes in our heads without any issue. I don't explode (like computers do in movies) when presented with a paradox. We just kinda go "Huh" and then move about our daily lives. it's strange to think that maybe paradoxes don't affect us that much, yet have such a profound effect on mathematics. I personally think it's due to the disconnect between our current mathematical theories and physical reality. We have much more to model!

          Cheers!

          Alyssa

            Hi Alyssa,

            thanks for reading my essay and I'm glad you enjoyed it!

            >> This is a very good point. but also, it seems that physical systems like biology don't seem to mind.

            I agree with you. It seems that the paradoxes cannot be "implemented" (in biological sytems or in physical computers). Only things that "make sense" can be implemented. Make sense is here defined with respect to the usual logic.

            >>It's interesting to think that we, as humans, can hold these paradoxes in our heads without any issue. I don't explode (like computers do in movies) when presented with a paradox.

            I don't explode (obviously) but I am left in a blocked state: I don't know how to solve it, and I cannot conclude that 'I am liar' is true nor false. So in this sense I am in a dead end - maybe that's the cognitive version of exploding :)

            >>I personally think it's due to the disconnect between our current mathematical theories and physical reality.

            I am also very interested in the question of whether one could define some mathematical models that circumvent some of these paradoxes. Or, alternatively, that model better the way we think. Or the two wishes together. The first wish has been addressed in alternative models of truth, such as Kripke's theory of truth and developments thereof. People investigating models of consciousness may be have addressed (in a perhaps oblique way) the second wish.

            Thanks again for your input :)

            All the best,

            Gemma

            Dear Gemma,

            I enjoyed reading your essay immensely! I feel like I have learnt a lot -- I was not aware before of the Boltzmann-machine and neural-network-types of universality, and it was nice to see the different examples put side-by-side. As universality is everywhere, undecidability must be too. And this raises several fascinating questions: does knowing transcend proving? Can the limitations be overcome by some other type of logic? What about the relation (as pointed out by Deutsch) to physics? Your essay gives a fascinating exploration of those ideas.

            One thing that suggests itself to be explored further, I think, is your statement that (Turing-type) universality only happens in digital systems. It feels like there must be some grain of truth to it. But it is probably not that easy to make it fully rigorous. For example, quantum theory has a continuous (non-digital) set of wave functions, and yet, it admits error correction (and contains a kind of "hidden" form of digitality)... So what kind of "digital" we need for reliable self-representation (for the liar paradox, as you pointed out) is perhaps a deeper question?

            All the best,

            Markus

              Dear Markus,

              thank you so much for your comments! I'm so glad you enjoyed the essay!

              >> quantum theory has a continuous (non-digital) set of wave functions, and yet, it admits error correction (and contains a kind of "hidden" form of digitality)... So what kind of "digital" we need for reliable self-representation (for the liar paradox, as you pointed out) is perhaps a deeper question?

              This is a very interesting question. But I don't know if the digitality needs to be "hidden" or mysterious. Consider natural language. At the spoken level it is continuous; yet, as a code, it is digital. The latter is reflected in the fact that it admits a representation with finitely many symbols. Listening to someone speak a language with their accent is doing error correction, i.e. mapping the sounds to a finite set of objects that give rise to a word and thereby an element of the language.

              I'd love to discuss this next time we meet :)

              Thanks again for reading the essay and for your very encouraging comments.

              All the best,

              Gemma

              a month later

              Hi Gemma,

              I really enjoyed your essay! I particularly appreciated all of the scholarship that went into your exposition of the topic. It seems to me that the role of universality is underrepresented in such discussions, so it was nice to see it centre stage in your essay. Concerning this: "Perhaps computable, provable, true, etc could be defined in a completely different yet-to-be-discovered way, which would rid them of the paradoxes." Do you have any ideas of what this would look like? Also, have you thought at all about whether universality for quantum computation (as opposed to classical computation) comes with any novel consequences for self-reference? Thanks!

                Hi Rob,

                Thanks so much for reading the essay, and I'm really glad you enjoyed it!

                >> Concerning this: "Perhaps computable, provable, true, etc could be defined in a completely different yet-to-be-discovered way, which would rid them of the paradoxes." Do you have any ideas of what this would look like?

                Not really. As mentioned in the essay, many people have tried to solve these paradoxes, mainly by building explicit or implicit hierarchies in the definition of truth, or computable, or knowable. (This is wonderfully explained in the Thomas Bolander's article on Self-reference - https://plato.stanford.edu/entries/self-reference/ ). But these hierarchies are infinite, so they only provide a solution in the limit, which I don't see as a solution. But perhaps we ought to take Markus P. Mueller's view and do not see this as a limitation, but rather as an indication that 'what is true / provable / knowable' is the wrong question.

                >> Also, have you thought at all about whether universality for quantum computation (as opposed to classical computation) comes with any novel consequences for self-reference?

                No, I haven't thought about that yet, but will definitely do. I would also love to discuss this with you :)

                Thanks again for reading and commenting, and all the best,

                Gemma

                Write a Reply...