Communications of the ACM
The Most Important Machine That Was Never Built
Church and Turing showed that some problems in mathematics are undecidable; no algorithm, however sophisticated, can tell us whether the answer is yes or no.
Credit: Kristina Armitage/Quanta Magazine;
Computation is a familiar concept most of us understand intuitively. Take the function f(x) = x + 3. When x is three, f(3) = 3 + 3. Six. Easy. It seems obvious that this function is computable. But some functions aren't so simple, and it's not so easy to determine if they can be computed, meaning they may never give us a final answer.
In 1928, the German mathematicians David Hilbert and Wilhelm Ackermann proposed a question called the Entscheidungsproblem ("decision problem"). In time, their question would lead to a formal definition of computability, one that allowed mathematicians to answer a host of new problems and laid the foundation for theoretical computer science.
The definition came from a 23-year-old grad student named Alan Turing, who in 1936 wrote a seminal paper that not only formalized the concept of computation, but also proved a fundamental question in mathematics and created the intellectual foundation for the invention of the electronic computer. Turing's great insight was to provide a concrete answer to the computation question in the form of an abstract machine, later named the Turing machine by his doctoral adviser, Alonzo Church. It's abstract because it doesn't (and can't) physically exist as a tangible device. Instead, it's a conceptual model of computation: If the machine can calculate a function, then the function is computable.
From Quanta Magazine
View Full Article
No entries found