Causality -- Consistency -- Complexity

par

Stefan Wolf

 Università della Svizzera italiana, Lugano, Suisse

La conférence sera présentée en anglais

Résumé:

Quantum theory predicts correlations that question fundamental causality. Dropping the latter, while still maintaining logical consistency, has dramatic consequences for the power of communication and computation. Such reasoning is in the spirit of Landauer's famous slogan "Information is Physical". A variant of its paradigmatic rival, Wheeler's "It from Bit", is the Church-Turing hypothesis: All physical processes can be simulated on a universal Turing machine. We use the tension between the two viewpoints to look for a purely intrinsic randomness notion and find one around the second law of thermodynamics. Quantum correlations, combined with Kolmogorov complexity as randomness, may reveal an all-or-nothing nature of the Church-Turing hypothesis: Either non-Turing computations are physically impossible, or they can be carried out by "devices" as simple as individual photons.