The Logic of Physical Law

Landauer's principle claims that "Information is Physical". Its conceptual antipode, Wheeler's "It from Bit," has since long been popular among computer scientists in the form of the Church-Turing hypothesis: All natural processes can be simulated by a uni-versal Turing machine. Switching back and forth between the two paradigms, motivated by quantum-physical Bell correlations and the doubts they raise about fundamental space-time causality, we look for an intrinsic, physical randomness notion and find one, namely complexity, around the second law of thermodynamics. Bell correlations com-bined with Kolmogorov complexity in the role of randomness imply an all-or-nothing na-ture of the Church-Turing hypothesis: Either beyond-Turing computations are physically impossible, or they can be carried out by "devices" as simple as individual photons. This latter result demonstrates in an exemplary way the fruitful interplay between physical and informational-computational principles.