文章目录
一、图灵机引入
二、公理化
三、希尔伯特纲领
四、哥德尔不完备定理
五、哥德尔 原始递归函数
一、图灵机引入
计算理论分为 形式语言与自动机 , 可计算部分 , 计算复杂性部分 ;
之前博客中介绍的 自动机 , 确定性有限自动机 , 非确定性有限自动机 , 正则语言 , 泵引理 , 上下文无关语法 , 下推自动机 , 都属于 形式语言 与 自动机 部分 ;
现在开始讲解 可计算部分 , 即 图灵机 ;
图灵机内容分为 : 图灵机 , 图灵机变形 , 丘奇-图灵论题 ;
二、公理化
希尔伯特纲领历史 , 希尔伯特所处的年代 , 最重要的学科是物理学 , 物理学中数学占很重要的一部分 ;
因此需要对数学进行公理化 , 数学中最重要的是实数 , 实数是由自然数扩张的 , 将自然数进行 公理化 ;
公理化 就是 给出几条公理 , 所有的定理 , 公式 , 推论 , 都是由几个公理推演出来的 , 参考几何学 ;
由公理推导出定理 , 由定理推导出推论 , 这套系统成为公理化系统 ;
公理化系统 是人类文明中的重要角色 ;
三、希尔伯特纲领
希尔伯特纲领 : 包含四部分内容 , 公理化 , 完备性 , 相容性 , 可判定性 ;
1 . 公理化 : 将整个数据进行公理化 , 在数学中的正确命题中 , 挑选出 有限多条命题作为公理 , 所有的命题都可以由这些公理推导出来 ;
2 . 完备性 :
计算机科学中有两大领域 , 语法 , 语义 ;
语法是符号运算 ;
语义是语法对应的现实含义 ;
命题逻辑的语法就是命题公式之间的运算 , 参考 【数理逻辑】命题和联结词 ( 命题 | 命题符号化 | 真值联结词 | 否 | 合取 | 析取 | 非真值联结词 | 蕴涵 | 等价 ) ;
完备性就是指所有的语法运算能够完全反应真实世界的真实运算 ;
3 . 相容性 ( 不矛盾性 ) :
在一个系统中 , 不能推导出一个命题 , 同时还能推导出该命题的否命题 ;
4 . 可判定性 :
存在一个算法 , 可以帮助我们判定任何一个命题是真命题还是假命题 ;
四、哥德尔不完备定理
哥德尔 否证明了上述 希尔伯特纲领 不可能实现 , 提出了 哥德尔不完备定理 , 否定上述命题需要对算法提出严格的数学定义 ;
整个数学不可能有一个完美牢固的基础 ;
哥德尔不完备定理 指出 推理的方法有很大的局限性 , 不是万能的 ;
中学算法很多都可以通过 推理 证明 计算 实现 ;
五、哥德尔 原始递归函数
原始递归函数 是由哥德尔提出的 , 该函数 定义在自然数集上 , 如下 :
{ h ( 0 , y ) = f ( y ) h ( x + 1 , y ) = g ( x , h ( x , y ) , y ) \rm
⎧⎩⎨h(0,y)=f(y)h(x+1,y)=g(x,h(x,y),y)
{h(0,y)=f(y)h(x+1,y)=g(x,h(x,y),y)
⎩
⎪
⎨
⎪
⎧
h(0,y)=f(y)
h(x+1,y)=g(x,h(x,y),y)
f , g \rm f , gf,g 这两个函数是已知的 , 根据这两个已知函数 , 定义一个新的函数 h \rm hh ,
h \rm hh 是二元函数 , 有两个分量 , 都是自然数 , 当第一个分量是 0 00 时 , h ( 0 , y ) \rm h (0, y)h(0,y) 通过 f ( y ) \rm f(y)f(y) 定义出来 ;
假设 g \rm gg 也是已知的 , 当 h \rm hh 的第一个分量不为 0 00 , 定义该分量值 , 使用递归方法定义 , 根据 h \rm hh 在 x , y \rm x , yx,y 上的值 , 定义 h \rm hh 的第一个分量是 x + 1 \rm x + 1x+1 时的值 ,
类似于数学归纳法思想 ;
