The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine

摘要

This book is an attempt by Petzold to make Turing's seminal paper, "On computable numbers, with an application to the Entscheidungsproblem" [1], accessible to ordinary readers; it has indeed turned out to be a successful attempt. "The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either 'True' or 'False' according to whether the statement is true or false" [2]. This problem formed one of the challenges put forward by mathematician David Hilbert in 1928.