Since the 1980s, quantum computing has given a practical technological arena in which computation and quantum physics interact excitingly, but it has not yet changed Turing’s picture of what is computable. There are also many thought-experiment models that explore what it would mean to go beyond the limits of the computable. Some rather trivially require that machine components could operate with boundless speed or allow unlimited accuracy of measurement. Others probe more deeply into the nature of the physical world. Perhaps the best-known body of ideas is that of Roger Penrose (7). These draw strongly on the very thing that motivated Turing’s early workâthe relationship of mental operations to the physical brain. They imply that uncomputable physics is actually fundamental to physical law and oblige a radical reformulation of quantum mechanics.

Superficially, any such theory contradicts the line that Turing put forward after 1945. But more deeply, anything that brings together the fundamentals of logical and physical description is part of Turing’s legacy. He was most unusual in disregarding lines between mathematics, physics, biology, technology, and philosophy. In 1945, it was of immediate practical concern to him that physical media could be found to embody the 0-or-1 logical states needed for the practical construction of a computer. But his work always pointed to the more abstract problem of how those discrete states are embodied in the continuous world. The problem remains: Does computation with discrete symbols give a complete account of the physical world? If it does, how can we make this connection manifest? If it does not, where does computation fail, and what would this tell us about fundamental science?