Well, happy belated birthday. November 18th was the 71st anniversary of the publication of Turing’s seminal paper, “On Computable Numbers with an Application to the Entscheidungsproblem“.
As described on Wikipedia:
In mathematics, the Entscheidungsproblem (German for ‘decision problem‘) is a challenge posed by David Hilbert in 1928. 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. The algorithm need not justify its answer, nor provide a proof, so long as it is always correct. Such an algorithm would be able to decide, for example, whether statements such as Goldbach’s conjecture or the Riemann hypothesis are true, even though no proof or disproof of these statements is known. The Entscheidungsproblem has often been identified in particular with the decision problem for first-order logic (that is, the problem of algorithmically determining whether a first-order statement is universally valid).
In 1936 and 1937, Alonzo Church and Alan Turing, respectively, published independent papers showing that it is impossible to decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible. This result is now known as Church’s Theorem or the Church-Turing Theorem (not to be confused with the Church–Turing thesis).
Shortly after finishing my undergraduate studies at MIT, I had the privilege of attending a brunch with Gian-Carlo Rota and some of his colleagues who represented a who’s who of local combinatorists. We got to talking about the halting problem, and someone asked me if it wasn’t just a contrived example of dubious relevance to computer science as a whole. Even then, I felt strongly that the halting problem, or it’s equivalent formulation in terms of Gödel’s incompleteness theorems, was at the heart of theoretical computer science, along with the still unsolved P vs. NP question.
So, happy birthday, dear Turing machine. You’re aged marvelously.
(Via The Register)