Titre : The physical Church-Turing thesis and the principles of quantum theory
Exposant : Pablo Arrighi
Notoriously, quantum computation shatters complexity theory,
but is innocuous to computability theory. Yet several works
have shown how quantum theory as it stands could breach
the physical Church-Turing thesis. We draw a clear line as to
when this is the case, in a way that is inspired by Gandy.
Gandy formulates postulates about physics, such as homogeneity
of space and time, bounded density and velocity of information ---
and proves that the physical Church-Turing thesis is a consequence
of these postulates. We provide a quantum version of the theorem.
Thus this approach exhibits a formal non-trivial interplay between
theoretical physics symmetries and computability assumptions.