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