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)
The Noisy Channel 
2 replies on “Happy Birthday, Dear Turing Machine”
I think that the P vs. NP question is academic nonsense.
See my post Is P vs. NP a practical problem?.
LikeLike
I read the post, and I can relate to your perspective. But I respectfully disagree.
Consider the birth of this problem, Kurt Gödel’s posthumously discovered 1956 letter to John von Neumann (http://weblog.fortnow.com/2006/04/kurt-gdel-1906-1978.html), in which Gödel broaches the question as to whether there are degrees on unsolvability.
The open P vs. NP question is as “academic” as the closed problem of the halting problem’s undecidability. You can argue that a lot of undecidable problems are academic nonsense because they have practical answers, e.g., kill the program if it hangs for more than a minute. Indeed, that is what the mathematician suggested in the brunch conversation.
But I see these questions as fundamental questions about the nature of the universe. Maybe that makes me a naive academic. Certainly it makes me more of a computer scientist than a software engineer. And, to be clear, I’m not the one putting up $1M for a proof. But you can be sure that, if I live to see the question resolved, I will celebrate that day as a milestone in the history of computer science.
LikeLike