文章目录
一、图灵机引入
二、公理化
三、希尔伯特纲领
四、哥德尔不完备定理
五、哥德尔 原始递归函数
一、图灵机引入
----
计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;...之前博客中介绍的 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;
现在开始讲解 可计算部分..., 即 图灵机 ;
图灵机内容分为 : 图灵机 , 图灵机变形 , 丘奇-图灵论题 ;
二、公理化
----
希尔伯特纲领历史 , 希尔伯特所处的年代 , 最重要的学科是物理学 , 物理学中数学占很重要的一部分...可判定性 :
存在一个算法 , 可以帮助我们判定任何一个命题是真命题还是假命题 ;
四、哥德尔不完备定理
----
哥德尔 否证明了上述 希尔伯特纲领 不可能实现 , 提出了 哥德尔不完备定理 , 否定上述命题需要对算法提出严格的数学定义...;
整个数学不可能有一个完美牢固的基础 ;
哥德尔不完备定理 指出 推理的方法有很大的局限性 , 不是万能的 ;
中学算法很多都可以通过 推理 证明 计算 实现 ;
五、哥德尔 原始递归函数
----