Universality Everywhere implies Undecidability Everywhere by Gemma De las Cuevas

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 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 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

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

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

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!