文章目录
一、丘奇-图灵论题
二、可判定性引入
三、图灵机语言
四、图灵机结果
五、判定机
五、部分函数与全部函数
六、可判定性定义
一、丘奇-图灵论题
为算法提供严格的数学模型 , 除了图灵机之外 , 还有其它的 3 33 种数学模型 :
① 可计算函数 ,数学方向 ;
② Lambda 演算 , 程序语言方向 ;
③ 登记计算机 ( Register Machine ) , 计算理论方向 ;
所有的数学模型 都为算法提供了严格的数学模型 , 这些数学模型之间是相互等价的 , 这是一个论题 , 不需要证明 ;
图灵机为算法提供了严格的数学定义 , 不需要证明 ;
丘奇-图灵论题 : 图灵机是计算的极限 , 是算法的严格的数学定义 ;
二、可判定性引入
经典的计算理论有 3 33 个基本概念 , 算法 ( Algorithm ) , 可判定性 ( Decidability ) , 有效性 ( Efficiency ) ;
之前讲的 都是 算法 ( Algorithm ) 范畴的 ;
同时 希尔伯特纲领 中 , 也要求了判定算法 , 希望存在一个算法 , 帮助判定任何一个数学命题的真假 ;
参考博客 : 【计算理论】图灵机 ( 图灵机引入 | 公理化 | 希尔伯特纲领 | 哥德尔不完备定理 | 原始递归函数 )
三、图灵机语言
给定一个字符串 , 将字符串写在带子上 , 让图灵机从开始状态 , 开始位置进行计算 ,
如果在计算过程中的 某个时刻 , 图灵机进入接受状态 , 那么称 该图灵机是接受这个字符串的 ;
将图灵机 M \rm MM 所 接受的所有字符串 w \rm ww 都放在一起 , 组成一个 集合 L \rm LL , 则该集合就是 图灵机 M MM 的语言 ;
使用符号化表示为 : L ( M ) = { w ∣ M 接 受 w 字 符 串 } \rm L(M) = \{ \ w \ | \ M 接受 w 字符串 \ \}L(M)={ w ∣ M接受w字符串 }
图灵机 计算模型 , 可以转换成语言 ;
四、图灵机结果
图灵机在 字符串 w \rm ww 上进行计算 , 可能有 3 33 种不同的结果 :
① 图灵机进入 接受状态 , 接受该字符串
② 图灵机进入 拒绝状态 , 不接受该字符串
③ 图灵机进入 L o o p \rm LoopLoop 不停机状态 , 出现循环
停机问题 , 在计算机科学中很重要 , 尽量避免出现 Loop 不停机状态 ;
五、判定机
简化图灵机 , 只研究特殊图灵机 , 该 特殊图灵机 在所有的字符串上 , 都会停机 , 任意给一个字符串 , 图灵机在该字符串上进行计算 , 要么进入接受状态 , 要么进入拒绝状态 ;
这种特殊的图灵机 , 被称为 “判定机” ;
五、部分函数与全部函数
部分函数 : 任意给定一个图灵机 , 对应一个 部分函数 , 给这个函数一个输入值 , 不会有结果 ; 图灵机进入 接受 / 拒绝 状态就有结果 , 进入 Loop 状态就不会有结果 ;
全部函数 : 任意给定一个输入值 , 都有唯一的输出值与之对应 , 这是函数 ; 这种函数称为 全部函数 ;
这里研究的特殊的图灵机 “判定机” , 判定机 只会进入 接受 / 拒绝 状态 , 因此判定机对应的是一个全部函数 ;
六、可判定性定义
如果一个语言是 图灵-可判定的 , 那么一定存在一个 判定机 判定该语言 ;
