The Beginning of Infinity: Explanations That Transform the World

by David Deutsch

Computations, as understood in Turing’s theory, are essentially the same thing as proofs: every valid proof can be converted to a computation that computes the conclusion from the premises, and every correctly executed computation is a proof that the output is the outcome of the given operations on the input. Now, a computation can also be thought of as computing a function that takes an arbitrary natural number as its input and delivers an output that depends in a particular way on that input. So, for instance, doubling a number is a function. Infinity Hotel typically tells guests to change rooms by specifying a function and telling them all to compute it with different inputs (their room numbers). One of Turing’s conclusions was that almost all mathematical functions that exist logically cannot be computed by any program. They are ‘non-computable’ for the same reason that most logically possible reallocations of rooms in Infinity Hotel cannot be effected by any instruction by the management: the set of all functions is uncountably infinite, while the set of all programs is merely countably infinite. (That is why it is meaningful to say that ‘almost all’ members of the infinite set of all functions have a particular property.) Hence also – as the mathematician Kurt Gödel had discovered using a different approach to Hilbert’s challenge – almost all mathematical truths have no proofs. They are unprovable truths.