  Landauer's principle claims that "Information is Physical." It is not
surprising that its conceptual antithesis, Wheeler's "It from Bit," has been
more popular among computer scientists --- in the form of the Church-Turing
hypothesis: All natural processes can be computed by a universal Turing
machine; physical laws then become descriptions of subsets of observable, as
opposed to merely possible, computations. Switching back and forth between the
two traditional styles of thought, 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 around the
second law of thermodynamics. Bell correlations combined with complexity as
randomness tell us that beyond-Turing computations are either physically
impossible, or they can be carried out by "devices" as simple as individual
photons.
