Home Archive catalogue Bio of Turing More about Turing Codebreaking Artificial Intelligence Computer history Photo gallery Books on Turing Cambridge archive Links Copyright |
## The Halting Theorem## By Jack Copeland## © Copyright B.J. Copeland, May 2000The Halting Theorem concerns what I will call the 'terminating program task' or 'TP task'. This task is to respond in accordance with the following rules to inputs of arbitrarily selected finite strings of binary digits: (1) Answer '1' if the input string is a program that will cause the universal Turing machine to execute only a (2) Answer '0' if the string is not a terminating program - i.e. if the string is either a Turing machine program that does not terminate or is not a well-formed Turing machine program at all. An example of a terminating program is one for finding the highest factor of a given integer, terminating on producing the answer. An example of a non-terminating program is one for calculating the digits of p (p having no last digit). The Halting Theorem says this: A The modern computer is based on the universal Turing machine. Since a finitely-operating universal Turing machine cannot carry out the TP task, nor can your computer. Indeed, even if your computer (or anyone else's computer) were given unlimited amounts of memory, and were allowed unlimited amounts of time in which to carry out an unlimited (although always finite) number of computations, your computer would still not be able to carry out the TP task. The TP task is a variation on a task invented by Turing in his 1936 article 'On Computable Numbers, with an Application to the Entscheidungsproblem'. In this article Turing stated and proved a theorem similar to the Halting Theorem. |

Loading

Site created and maintained by Jack Copeland

All rights reserved

All rights reserved