Turing's thesis and physics
Matthew Szudzik
Abstract:
Alan Turing claimed that every mathematical function which can be
effectively computed by humans is a function that can be computed by a
Turing machine. This claim, known as Turing's thesis, serves as the
theoretical foundation for computer science. It guarantees, for
example, that if a human can imagine an explicitly-described procedure,
then that procedure can be automated by a computer.
In the decades since Turing proposed his thesis, various generalizations
have been proposed. For example, the physical generalization of
Turing's thesis states that any function which can be effectively
computed by a physical process is a function that can be computed by a
Turing machine. But this simple generalization has been historically
difficult to formalize. What is the correct formal definition of the
physical generalization of Turing's thesis? We will discuss some of the
historically significant attempts to answer this question, and describe
our own recently-proposed solution.