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.