数学家、数学学生和晚上睡觉时幻想着拥有埃尔德什数的秘密数学爱好者：我想听听你们的意见。

尤其是我要打电话给罗伯特·欧文·索尔（Robert Irving Soare）（请注意，是开玩笑）。

在最近一篇题为《可计算艺术家——论图灵和米开朗基罗》的文章中，我介绍了索尔的一篇短文，其中索尔提出了一个问题：为什么是图灵而不是丘奇？

鉴于丘奇（毕竟丘奇是老师）解决了现在与图灵相关的许多问题，为什么图灵的工作被认为是权威的，而可怜的丘奇却被贬低了？

也许图灵只是超越了他的老师，就像老功夫电视剧中的 Kwai Chang Caine 一样，经过多次尝试，他终于从老师手中抢到了鹅卵石。

或者这也许与图灵戏剧性的人生故事和英年早逝有关，而丘奇——异性恋，已婚，据我所知没有被判过任何重大罪行——过着更加平静的生活，活到了 92 岁。在他最著名的肖像中，他看起来非常开朗。

索尔在他的论文中认为，图灵的作品比丘奇的作品更美，将丘奇与艺术家多纳泰罗（Donatello）相提并论，多纳泰罗很伟大，但不是米开朗基罗（Michelangelo），而他将图灵与艺术家米开朗基罗相提并论。

Reddit 上的一个人对此论点并不满意。他最初写信是为了回应我的另一篇帖子（艾伦·图灵是“我们这个世纪的关键人物”，马文·明斯基），他问了索尔问过的同一个问题：为什么是图灵而不是丘奇。他写道：

“那阿隆佐·丘奇呢？据我所知，这是准确的：

- λ演算先于图灵机，

- 阿隆佐·丘奇是图灵的博士导师

- 斯蒂芬·克莱恩（丘奇的另一名学生）证明了通用图灵机和λ演算等价，并用它们来定义可计算性

那么答案是什么？

现在，我知道约翰·冯·诺依曼（冯·诺依曼机器以他的名字命名）在建造 ENIAC（维基百科认为是“第一台通用电子计算机”）期间曾向他的同事推荐了一篇图灵论文，但我仍然对将图灵提升到丘奇之上感到好奇。”

我相信阅读此帖子的其他人比我更了解此事，因此，听听我们为什么强调图灵（比如，与他在战时破解加密无关的原因）会非常有趣。

我让他看了我关于索尔论文的帖子，但他仍然不相信：

“我真的不认为美学论证是图灵被记住而不是丘奇的原因，这一点很有说服力。

原因有二：

1，人们不会说，“嘿，艾伦·图灵真的创造了一个概念上很美的通用可计算性版本。当然，阿隆佐·丘奇是第一个提出这个观点的人，他提出的结果和图灵的一样’强大’，但丘奇的模型吸引力要小得多。”事实上，他们用你的博客文章来框定讨论——发现本身的重要性和力量。我愿意接受这样一种可能性，即 lambda 演算与计算机的联系不那么明显，因此它对人们的影响能力较弱，但我从未听说过这种论点。

2，与 lambda 演算的优雅和概念清晰度相比，图灵机简直丑陋不堪。诚然，我无法绝对肯定这一说法，但既然我们谈论的是流行概念，那么我引用流行品味（相对于数学/理论计算机科学的流行程度而言）也是公平的。数学之美的一般标准是优雅——即用小东西获得大东西。在我看来，lambda 演算似乎优雅得多，我认为如果你对数学知识渊博的人进行调查并让他们比较两者，他们会压倒性地发现 lambda 演算比通用图灵机更有吸引力。”

好吧，正如我向他坦白的那样，我没有足够的数学知识来真正参与这场争论，所以我提出了两点建议。首先，我会在这里发布他的评论，并邀请所有人发表评论；其次，我会专门写信索尔，看看我们能否说服他，本着友好辩论的精神，做出回应。

所以挑战已经下达。索尔博士，如果你想捍卫你的论文，这是你的选择。我通知你这个挑战的电子邮件现在正在发给你的路上。

至于你们其他人，继续努力吧！

“美”的论点有说服力吗？

或者也许还有其他更令人信服的原因，说明为什么图灵的光芒部分掩盖了丘奇的光芒？

您可以使用评论页面或给我写信，地址是 nas@homoartificialis.com。

原文：

https://theturingcentenary.wordpress.com/2012/02/18/turing-vs-church-and-the-great-mathematics-throw-down/

Turing vs. Church and the Great Mathematics Throw-Down

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.

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:

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.

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.