A quantum extension of Gandy’s theorem: Church-Turing thesis and quantum theory

October 22 2010
Types d’événements
Séminaire LARSIM
Pablo Arrighi
SPhT Bât 774 Salle C. Itzykson,
22/10/2010
from 11:00

Joint work with Gilles Dowek. We tackle the question of the interplay between computability and quantum theory, 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 as a consequence. The authors provide a quantum extension of the result.

Université de Grenoble