不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

图灵致马克斯·纽曼关于逻辑的通信(c.1940) 精选

已有 2062 次阅读 2023-11-7 01:47 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

Copeland的书“The Essential Turing”中收集了图灵1940年写给他的老师、同事和朋友的两封信,其中一封中图灵写道:

哥德尔的论文终于到了我手里。我现在对它非常怀疑,但我还得再研究一下 Zermelo–v. Neumann 系统,然后才能把反对意见白纸黑字写下来。

也就是说,图灵在1940年才读到哥德尔的原文,而在1936年他写那篇著名论文时并没有读哥德尔的原文,只是知道哥德尔不完备性定理的结论。

一,Copeland介绍图灵与纽曼关于通信的背景如下:

19399月对德战争爆发后,图灵离开剑桥大学,前往布莱切利公园(Bletchley Park)担任密码破译员,该公园是政府密码和密码学校的战时总部(见下文Enigma)。1940 年初,图灵收到剑桥数学家纽曼的来信,纽曼是图灵的老师、同事和朋友。3 23日,图灵在皇冠旅馆(位于Shenley Brook End小村)的住所给他回了信:亲爱的纽曼,很高兴收到你的来信,因为我需要一些刺激来让我开始思考逻辑问题。这是图灵在纽曼离开剑桥前往布莱切利公园之前的 17 个月里写给纽曼的5封信的第一封信。

在他的第一封信中,图灵同意(大概是应纽曼的要求纽曼的信件似乎没有保存下来)[纽曼]了解……转换计算的技巧。转换计算或 "l-计算 "是丘奇(Alonzo Church)的成果,图灵曾于1936年至1938年在普林斯顿师从丘奇。图灵的信中大部分是关于转换计算的详细评论,经常阐明图灵所谓的丘奇笔记中的材料丘奇笔记是一份题为数学逻辑的大部头排印稿,在普林斯顿和其他地方流传,纽曼显然读过它。

他们关于丘奇工作的通信发表在他们的联合论文《丘奇类型理论中的一个形式定理》中,该论文于 19415月提交给丘奇的《符号逻辑杂志》,并于19423月发表。图灵偶尔会在下班后照常上班。 ,晚上在温暖明亮的办公室里做自己的数学研究,而不打扰白天的睡眠。

本文所刊载的这两封书信中最有趣的是,图灵在其中的大量段落中脱离了他对丘奇作品的评论,阐述了自己的观点。这些优雅的段落提供了图灵关于数学逻辑基础的思想,而这些思想在他的其他著作中是找不到的。

尤其重要的是标题为“Intuition. Inspiration. Ingenuity”,其中他讨论了逻辑学中的不可解性和不完备性结果,并解释了他的序数逻辑学(第3章)的基本思想; “直觉与巧思讨论了图灵机的可证明性在多大程度上接近数学真理; “完备性定理涉及第3章中建立的完备性定理; “结果比较了两个逻辑结果概念。这些章节中偶尔包含转换计算的公式,但这些公式对图灵的观点来说并非必要,不熟悉计算符号的读者也不必担心。

二,图灵与纽曼通信摘录

直觉,灵感,巧思Intuition. Inspiration. Ingenuity

我不确定我用的直觉这个词是否正确,或者你的灵感是否会更好。 我倒觉得你是在用灵感来涵盖我所说的巧思 举一个巧妙的具体例子,假设我想要一个公式 Q,其性质是

我当然可以搜索所有公式Q的枚举,并对 Q(x)进行转换(通过 "对角线过程",比可能不计其数的转换过程节省时间),但如果在我这样做的时候,某个旁观者写下了

并说试试看,我应该说他通过巧思找到了一个公式。 在这种情况下,无需担心公式是如何得出的。 它的正确性可以通过简单的转换或同样没有争议的事情来验证。 这不是你所说的灵感吗?

关于逻辑系统的直接的不可解性或不完备性结果是这样的

  1. 不能指望能够解决一个系统的EntscheidungsproblemOne cannot expect to be able to solve the Entscheidungsproblem for a system)。

  2. 不能指望一个系统会涵盖所有可能的证明方法(不适用于有限函数计算)(One cannot expect that a system will cover all possible methods of proof (does not apply to ‘restricted function calculus’)。

在我看来,在你关于我们希望逻辑体系做什么的论述中,你似乎只考虑到了a),而没有考虑到b)。我同意你的观点,只要我们能对 b)项视而不见,也就是说,我们并不是真的想通过枚举来进行证明,而是先找到一个,然后再检查它是否正确。不过,如果有了检查的方法,这种方法在理论上总是可以被更长的方法取代的,尽管在实践中并不可行。例如,证明的枚举法就是从所有可能的符号序列的枚举法中通过剔除那些没有通过检验的符号序列而得到的。当我们考虑到 b) 时,就不得不承认需要的不是一种而是多种检验方法。在写序数逻辑时,我就想到了这种想法。在证明中,实际上有大量的艰苦工作和一定的独创性,而在大多数情况下,实际的证明方法是众所周知的。难道我们就不能更清楚地说明,哪些地方需要煞费苦心,哪些地方需要独具匠心,哪些地方需要证明方法吗?事实上,我们就不能简明扼要地说明每个证明的地位吗?序数是为了简明扼要地说明证明的地位。

完备性定理

当然,我的完备性定理(PA 等)的证明对于实际提出证明的目的是完全无用的。只有当 A 相当简单,并且很容易被识别为一个序式时,PA 才是一个令人信服的逻辑。完备性定理的写作视角与其他大多数定理截然不同,因此容易导致混淆。我认为,这个证明所做的一切,都是为了给某些 "哥德尔不完备性定理 "的证明提供一种保险。

一旦出现必须证明所使用的公式是序数公式的问题,我们就又回到了单一逻辑的观点,除非所使用的证明是不同的,是一种宣传而不是形式证明。

。。。

哥德尔的论文终于到了我手里。我现在对它非常怀疑,但我还得再研究一下 Zermelo–v. Neumann 系统,然后才能把反对意见白纸黑字写下来(Godel’s paper has reached me at last. I am very suspicious of it now but will have to swot up the Zermelo–v. Neumann system a bit before I can put objections down in black & white)。

参考文献:

https://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf




https://m.sciencenet.cn/blog-2322490-1408713.html

上一篇:关于“整合(integration)” - 两只骡子的寓言
下一篇:不动点定理(fixed-point theorem)

2 崔锦华 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-2-29 09:19

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部