Gibbons Lecture Series: Alan Turing and the Unsolvable Problem
To Halt or Not to Halt - That is the Question
Speaker: Professor Cristian S. Calude, Department of Computer Science, The University of Auckland
Professor Calude has been with our Computer Science Department since he left his native Romania in 1992. He has made contributions to many areas of theoretical computer science with continuing interest in Algorithmic Information Theory and Quantum Computing. His achievements are being recognised at a special conference to celebrate his entering his 7th decade in February 2012.
Synopsis: The "decision problem" (Entscheidungsproblem in German), proposed by the mathematician David Hilbert, was to devise a mechanical method for deciding whether or not any specific mathematical statement has a proof. In his first important accomplishment, Turing proved that no such method existed. In doing so, he introduced his own abstract computer - the Turing Machine - to capture what was meant by a mechanical method. In passing, Turing showed that one Universal Turing Machine, mixing instructions and data in its memory, could achieve the work performed by any such machine - so explaining the power and generality of the modern computer.
Additionally, Turing showed that there were tasks that were beyond the power of any ordinary computer, in particular the halting problem, which is to decide whether or not any computer program will loop or run endlessly. Turing's work laid the foundation for the theory of computing. Since his time this field has expanded in many ways. Among them are the use of Turing's notions to capture the concept of randomness and to investigate the nature of problems that, although unsolvable by ordinary computers, may be cracked by more unconventional means.