Turing vs. Church and the Great Mathematics Throw-Down

“A Great science fiction detective story”
- Ian Watson, author of The Universal Machine

Days to Centenary: 126

Mathematicians, math students, and secret math hobbyists who go to sleep at night fantasizing about having an Erdös number: I  want to hear from you.

And in particular I am calling out one Robert Irving Soare (playfully, mind you).

In a recent post entitled The Computable Artist — On Turing and Michelangelo, I featured (and linked to) a brief paper by Robert Irving Soare in which Soare asks the question: why Turing and not Church?

Given that Alonzo Church — who was after all Church’s teacher — worked out so many of the things that are now associated with Turing, why is Turing’s work considered definitive while poor Church is relegated to the background?

Maybe Turing simply overtook and surpassed his teacher, like Kwai Chang Caine in the old Kung Fu television series, who was able — after many attempts — to finally snatch the pebble from his master’s hand.

Or perhaps it had more to do with Turing’s dramatic life story and untimely end, while Church — heterosexual, married, not convicted of any significant crimes that I know of — lived a more sedate existence and survived until the ripe old age of 92.  In his most famous portrait, he looks positively cheerful.

Alonzo Church, looking unperturbed by the fame of his student, Alan Turing

So what’s the answer?

Soare argued in his paper that Turing’s work was more beautiful than Church’s comparing Church to the artist Donatello, who was great and all, but who was no Michelangelo, the artist to whom he compares Turing.

This argument didn’t sit well with one person on Reddit.  He originally wrote to respond to a different post of mine (Alan Turing is “the Key Figure of Our Century,” Marvin Minsky), asking the same question Soare had asked: why Turing and not Church.  He wrote:

Wha’bout Alonzo Church? This is accurate to the best of my knowledge:

• Lambda Calculus precedes the Turing Machine,
• Alonzo Church was Turing’s PhD Advisor
• Stephen Kleene (another of Church’s students) showed Universal Turing Machines and Lambda Calculus to be equivalent and used them to define computability

Now, I understand that John Von Neumann (the man for whom Von Neumann Machines are named) referred his colleagues to a Turing paper, specifically, during the building of the ENIAC (considered, via Wikipedia, “the first general-purpose electronic computer), but I’m still curious about elevating Turing about Church.

I’m sure someone else reading this thread knows more about the matter than I do, so it’d be very interesting to hear about why we emphasize Turing (say, a reason that isn’t related to him cracking encryption during wartime).

I directed him to my post on Soare’s paper, but he remained unconvinced:

I truly don’t find the aesthetic argument as the reason Turing gets remembered over Church to be very convincing.

For two reasons:

1. People don’t say, “hey, Alan Turing really made a conceptually-beautiful version of general computability. Sure, Alonzo Church was there first and stated results every bit as ‘powerful’ as Turing’s, but Church’s model is so much less appealing.” In actual fact, they frame the discussion in the terms your blog post does—the importance and power of the discovery, itself. I’m open to the possibility that somehow lambda calculus has a less obvious connection to computers and that (as a result) it had less ability to influence people, but I’ve never heard that argument made.
2. Turing machines are downright ugly compared to the elegance and conceptual clarity you find in the lambda calculus. This is admittedly a statement that I can’t make absolute, but since we’re talking about popular conception, it’s fair of me to reference popular taste (popular relative to a piece of math/theoretical computer science’s capacity to be so). A general criterion for mathematical beauty is elegance—i.e. getting a lot out of a little. Lambda calculus to me seems ridiculously more elegance, and I think if you polled the mathematically literate and asked them to compare the two, they’d overwhelmingly find the lambda calculus more appealing than the Universal Turing Machine.

Well, as I readily admitted to him, I don’t have enough math to really enter this fray, so I prooposed two things.  First, that I would post his comments here and invite everyone out there to comment, and second that I would specifically write Soare and see if we could persuade him, in the spirit of friendly debate, to respond.  

So the gauntlet has been thrown down.  It’s your play Dr. Soare, if you care to defend your thesis.  My email informing you of this challenge is on its way to you even now.

And as for the rest of you, have at it!

Is the “beauty” argument persuasive?

Or is there perhaps some other reason that seems more convincing to you as to why Turing’s star has partially eclipsed Church’s?

You can use the comment page or write me at nas@homoartificialis.com.

The Computable Artist — On Turing and Michelangelo

“A Great science fiction detective story”
- Ian Watson, author of The Universal Machine 

Days to Centenary:  162

Turing and the Art of Classical Computability [12pp., download PDF here] sounds like the name of yet another derivative paper, maybe a survey or a restatement of established mathematical principles.

No, Turing-ites!

Because its author, Robert Irving Soare, who has written several papers in honour of the Alan Turing Year, is using the word “art” in the way you and I would use it when visiting a gallery. He means art as in a skill, but also art as in an aesthetic endeavor.

Soare, who is  the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science at the University of Chicago, writes:

Mathematics is an art as well as a science. It is an art in the sense of a skill as in Donald Knuth’s series, The Art of Computer Programming, but it is also an art in the sense of an esthetic endeavor with inherent beauty which is recognized by all mathematicians.

In his essay, Soare asks why Turing receives so much credit with respect to the issue of computability when Alonzo Church, as he puts it “got it right and … got it first.”

Soare answers this question by reference to Turing’s mathematical artistry through a side-trip into classical art and a comparison of Donatello, to whom he likens Church, and Michelangelo, whom he compares to Turing.

Michelangelos '"David" (detail)

Soare’s argument is entertaining and enlightening, and will probably be so even for those who don’t end up convinced by his argument, so I recommend reading the paper yourself.  At twelve pages, it’s admirably economical and will more than reward the short time it takes to read it.

Michelangelo's Pietà, completed when he was twenty-four, the same age as Turing when he published his "On computable numbers with an application to the Entscheidungsproblem."

Soare insists — as many commentators have done in relation to scientific disciplines that can be practiced in a theoretical manner, such as mathematics and physics — that math is not simply a matter of getting the right result, but of doing so in a way that is elegant and that may therefore be judged aesthetically:

Mathematicians are not assigned projects like building bridges. Like artists, they choose which problems to work on according to taste and beauty. Like artists, what they produce is evaluated on the basis of beauty as well as mathematical results. The greatest results are those arising from a completely new vision and a profound intuition into the area.

I’m not a mathematician and therefore not in much of a position to judge the relative aesthetics of Turing’s work myself, but if it does constitute great art that bears comparison with Michelangelo I wouldn’t be much surprised.

Great art can be judged by many particulars, but one of its hallmarks is its capacity to be endlessly fecund, and with all of the things that have flowed from  Turing’s brief period of creation his work is certainly that.