Universality everywhere: from spin models to automata
Date
Thursday, January 16, 2020 15:00 - 16:15
Speaker
Gemma de las Cuevas (University of Innsbruck)
Location
Mondi Seminar Room 2, Central Building
Series
Seminar/Talk
Tags
General Interest Seminar
Host
Bernat Corominas-Murtra
Contact
Url
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. I will argue that there is universality eveyrwhere and will discuss this concept of universality in two domains: for spin models and for automata (or, equivalently, formal languages). I will explain the first step toward linking them rigorously, by which we describe spin hamiltonians as automata. The latter leads to a new complexity measure of hamiltonians, with a different threshold between easy and hard than the computational complexity of the ground state energy problem.