If I have one hope for my book, The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine , it is to help readers understand the difference between Turing's original Turing Machine, and the Turing Machine as it's commonly encountered in college courses and textbooks. Two decades after Turing's paper that introduced his computing machines, the Turing Machine was reformulated by Stephen Kleene in Introduction to Metamathematics (1952) and Martin Davis in Computability and Unsolvability (1958). These reformulated machines — which generally compute functions — dominate the current literature on computability. The "halting problem" (the term is Martin Davis's) involves the existence of a general algorithm to determine whether an arbitrary machine finishes properly and halts, or whether it goes bad and runs forever. As I've mentioned before ( 2006-08-11 , 2007-11-26 , 2007-12-02 , 2008-05-12 ), it is not correct to associate
Read More...