Can Quantum Computing Resolve the Turing Halting Problem?

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