Gemma De las Cuevas (Innsbruck): From simplicity to universality and undecidability

Why is it so easy to generate complexity? I will suggest that this is due to the phenomenon of universality - essentially every non-trivial system is universal, and thus able to explore all complexity in its domain. We understand universality in spin models, automata and neural networks. I will present the first step toward rigorously linking the first two, where we cast classical spin Hamiltonians as formal languages and classify the latter in the Chomsky hierarchy. I will also talk about the other side of the coin of universality, namely undecidability, which comes from self-reference and negation as in "I am a liar". I will propose that there is undecidability everywhere, namely, that essentially every non-trivial question of a system is undecidable. I will also share some thoughts about the reach of universality and undecidability in other disciplines. Why is it so easy to generate complexity? I will suggest that this is due to the phenomenon of universality - essentially every non-trivial system is universal, and thus able to explore all complexity in its domain. We understand universality in spin models, automata and neural networks. I will present the first step toward rigorously linking the first two, where we cast classical spin Hamiltonians as formal languages and classify the latter in the Chomsky hierarchy. I will also talk about the other side of the coin of universality, namely undecidability, which comes from self-reference and negation as in "I am a liar". I will propose that there is undecidability everywhere, namely, that essentially every non-trivial question of a system is undecidable. I will also share some thoughts about the reach of universality and undecidability in other disciplines.