Abstract

The Church-Turing thesis states that a function is computable by “reasonable means” if and only if it is computable by a Turing machine. In this talk, we examine computation that is not computable by reasonable means, and is therefore not computable by a Turing machine. Several theoretical hypermachines will be introduced including Turing’s Oracle machines and so-called Zeno machines. We’ll discuss how these machines can “compute the uncomputable”, and discuss the issues with physically implementing such machines. We conclude that it is still unclear whether hypercomputation is possible within our universe, with the answer having serious implications for mathematics, physics, and philosophy.