数学联邦政治世界观
超小超大

数理逻辑-余俊伟(三) (4-2)

能行过程:在数理逻辑和计算机科学中,算法也是一个能行过程或能行方法,即能解决某问题。能行过 程的特点与算法基本是一样的,区别在于:前者稍显粗略,因为它允许用自然语言描述, 不过可读性却比较强;后者十分严格,是用选择伪代码、流程图、控制表、程序设计语 言等进行描述的,不允许使用自然语言描述,不过可读性不是很强。因此,算法一定是 能行过程,而能行过程不一定是算法,但能行过程却一定可以通过语言的转换变成算法。

5.2.2 图灵可计算性

此节先说了图灵机如何运算,然后用图灵机描述可计算性。涉及部分函数的概念。

不同书不同图灵机,但等价。

5.2.3 部分递归函数

除了图灵机,可计算性有另一种精确描述:哥德尔–克林尼式的数学描述。它 可以从最简单的、直观的可计算函数逐步地生成(全部的)直观的可计算函数利于人们把握具体的直观可计算函数。最终,我们还会说明所有的部分递归函数都是图灵可计算的。

原始递归函数:给出0也就是零值函数,给出后继函数,给出投影函数,然后复合函数。再原始递归。原始递归函数类是包含初始函数并对复合和原始递归封闭的最小函数类。称函数 f 是原始递归的,如果它属于原始递归函数类。引入极小算子(minimalisation operator)和正则(regular)极小算子。定义递归函数和部分递归函数。递归函数类是包含初始函数并对复合、原始递归和正则极小算子封闭的最小函数类;称函数f是递归的,如果它属于递归函数类。 部分递归函数类是包含初始函数并对复合、原始递归和极小算子封闭的最小函数类; 称函数f 是部分递归的,如果它属于部分递归函数类。 递归函数类不等于图灵可计算函数类,它只是图灵可计算函数的真 类,因为下文会证明图灵可计算函数类就是部分递归函数类。

5.2.4 丘奇图灵论题

丘奇给出 λ-可定义函数这种可计算性描述的同时,还提出了丘奇论题:直观上可计算的函数类就是 λ-可定义函数类。图灵 1936 年给出图灵可计算函数这 种可计算性描述后,1937 年又证明了图灵可计算性和 λ-可定义性的等价。用图灵可计算函数对丘奇论题进行了重新表述,得到丘奇–图灵论题:直观上可计算的函数类就是图灵可计算函数类。

5.2.5 可计算枚举集

可计算集和可计算枚举集又可叫递归集和递归可枚举集。

5.3 第一不完全性

设 T 是可计算公理化的、一致的 L1-理论。作为目标,希望 T 是完全的, 即 T 等于 Th(M)。不妨进一步假设,能够用语言 L1 谈论自身基本语法和自 公理到定理的证明。一般说来,只要 L1 可以谈论自然数的性质,那么 L1 就 能通过编码的方式谈论自身语法。

罗宾森算术比皮亚诺算术要弱很多,一来定理表述可以更一般, 二来标准算术模型的真语句集与罗宾森算术的差异比其与皮亚诺算术的差异更大。

本节哥德尔第一不完全性定理的证明思路是:首先证明所有的可计算关系都是可表 示的,然后证明算术化的语法概念是可计算的,而后在此基础上证明不动点引理,从而 基于可表示的证明概念由不动点引理推出哥德尔第一不完全性定理。

5.3.1 罗宾森算术

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

兔子先生的兔子洞(无限) 连载中
兔子先生的兔子洞(无限)
祈念qinian
笙笙宝宝和乐乐宝宝的头像先凑合一下吧≡ω≡~假期里练一练自己画!
0.7万字9个月前
月老桃清 连载中
月老桃清
多陌
已完结。改名为:《迷局》穿越各个小世界,完成神帝的任务,却不料发现了一些震惊的秘密。
43.5万字8个月前
快穿:亿万分之一的甜 连载中
快穿:亿万分之一的甜
兔缨
【已签约】夏唯安在参加男神的演唱会时被踩死了。在系统口中得知自家好闺蜜被上铺的东西砸死时,她仰天大笑三声,决定救自己还有闺蜜。只是前面有些位......
23.7万字8个月前
天域第一神 连载中
天域第一神
千珑樰
林清自幼受尽人间疾苦,一颗坚韧之心不肯屈服。奈何命运无常。天道破损。修天道。战北渊。手握太星之力,杀遍天下负罪之人。守护红颜知己。力争一线生......
19.2万字8个月前
天蛇白矖 连载中
天蛇白矖
牛奶炖榴莲
天蛇白矖(xi,三声)明明记得自己已经亲手被“墨圣禹”杀死!醒来却身在人界,还是香士世家,白家的大小姐?莫不是被别人用重魄灯重塑肉身?只是,......
15.5万字8个月前
陈情令——魏无羡重生之守护 连载中
陈情令——魏无羡重生之守护
魏无靖
这一辈子一定要保护好师姐,虞夫人,江叔叔,温情,温宁
0.3万字8个月前