Double discovery 01: Turing & Church

POSTED: October 20, 2020

I have decided to keep notes about double discoveries whenever I come across them, because so far I seem to have managed to forget them as fast as I find them.

Double discoveries? A lot of discoveries, a lot more than you might think, got invented independently by more than one person, or more than one group.

Calculus provides the standard example for this.

“Calculus, known in its early history as infinitesimal calculus, is a mathematical discipline focused on limits, continuity, derivatives, integrals, and infinite series. Isaac Newton and Gottfried Wilhelm Leibniz independently developed the theory of infinitesimal calculus in the later 17th century. By the end of the 17th century, each scholar claimed that the other had stolen his work, and the Leibniz-Newton calculus controversy continued until the death of Leibniz in 1716.”

So says Wikipedia.

Today I listened to a podcast about Alan Turing and I learned that the universal Turing machine also got invented twice. Or almost.

Turing developed his calculations as the result of a challenege – the Entscheidungsproblem, or “decision problem” – posed by David Hilbert and Wilhelm Ackermann in 1928.

“In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of “effectively calculable” is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.”

So, once more, says Wikipedia.