The Art of Classical Computability
Why Turing and not Church?
Why give so much credit to Turing and not to Church? Church was a
full professor at Princeton in 1936 when Turing was a mere graduate
student. Church had studied Hilbert's papers a decade before Turing
and had explained them to his Princeton thesis adviser, Oswald Veblen.
Church was working in the Herbrand-Godel recursive functions defined
by Godel, the most eminent logician at the time. These used the
concept of recursion (induction) which had appreared in mathematics
since Dedekind [1888]. In contrast Turing machines were a fanciful
new invention without such a concise, mathematical definition in a
familiar formalism. By 1934 Church and Kleene had shown that most
number theoretic functions were $\lambda$-definable and therefore
recursive, giving clear evidence for Church's Thesis.
Church was the first to propose Church's Thesis when even Godel did
not believe it. Church got it right and he got it first. The
effectively calculable functions are the recursive functions.
By any purely quantifiable evaluation Church's contribution was at
least as important as Turing's. However, characterizing human
computability was not a purely quantifiable process.
Why Michelangelo and not Donatello?
Donatello
Donatello (1386--1466) was a sculptor in Florence. In 1430 he created
the bronze statue of David his most famous work.
Donatello's bronze statue of David (1430)
was a remarkable work, innovative in many ways, the first
free-standing nude statue since ancient times, the first major work of
Renaissance sculpture. While most scuptors showed David holding the
head of the giant, Donatello showed David placing his foot on the
giant's head while holding a sword in his other hand. It is an
allegory of civic virtues triumphing over brutality and irrationality.
Michelangelo
Michelangelo's marble statue of David (1501-1504)
is the most famous statue in the world. Michelangelo broke away from
the traditional way of representing David, with sword in hand and with
the giant's head at his feet (as with Donatello). Michelangelo has
caught David tense with increasing power as he is about to go to
battle. Michelangelo places him in perfect contraposto outdoing the
Greek representations of heros. In painting several artists had
decorated the walls of the Sistine Chapel but Michelangelo's ceiling
there is incomparable.
Michelangelo and Turing
Michelangelo and Turing both completely transcended conventional
approaches. First they both created something completely new
from their own visions, something which went far beyond the
achievements of their contemporaries. Second, both emphasized the
human form. Michelangelo brought out the human form in his
statues and in the Sistine ceiling with magnificient human
figures often shown in contraposto.
Turing left behind the formal systems of lambda-definable or
recursive functions. Turing searched into how a human being actually
computes. He built his theoretical automatic machine (a-machine) to
realize this process and he demonstrated that his automatic machine
captured all of human computing.
Soare paper
Turing and the Art of Classical Computability
This paper will appear in the volume, Alan Turing His Work and
Impact, Ed. Cooper and van Leuwan, Elsevier, 2012.
