In 1934 Alan Turing graduated with distinction in the mathematical Tripos examination and a year later, at the tender age of twenty-two, was elected to a Fellowship at King's College (Cambridge). In 1935 he attended a course in the Foundations of Mathematics given by the topologist MHA (Max) Newman. The lectures considered such concepts as the consistency, completeness and decidability of various formal axiomatic systems and the Godel incompleteness results but it was the bntscheidungsproblem (Decision problem), of determining whether or not a given formula of first-order logic is valid, which captured his attention and dominated his thinking from the Summer of 1935 until the early Spring of 1936. David Hilbert, who posed this problem originally in the 1920s, called it the fundamental theorem of mathematical logic for he surmised that an algorithmic solution to it would entail that any mathematical problem would be decided by an algorithm.
展开▼
