Can Quantum Computing Resolve the Turing Halting Problem?
Prof Tien Kieu
Centre for Atom Optics and Ultrafast Spectroscopy, Swinburne University of Technology
3.30pm, Friday 19 October 2001, Seminar Room (AR103), Graduate Research School
The Turing halting problem asks for a universal process according to which a finite number of steps
could determine whether an arbitrary computer program would or would not halt upon starting from an arbitrary (but legitimate)
input. The application of the Cantor's diagonal arguments is thought to have solved this Turing problem: there does not exist
such a universal process. This negative answer is an example of semi-computable functions, restricting what one could do with
computers. It has also led to the Church-Turing thesis which equates the intuitive notion of computability to be exactly what
can be done by the mathematically well-defined Turing computation, and not more.
After reviewing the Turing halting problem and its standard proof, I will briefly introduce the
concepts of quantum computation and present a quantum algorithm which, contrary to the widely accepted folk lore above, may
be able to resolve the halting problem in a positive way. Thus, it seems that computability is not restricted by the Church-Turing
thesis but further extended by quantum computation.
Back to 2001 programme