网站模板和定制的区别,专门搜索知乎内容的搜索引擎,公众号微官网,湛江高端网站建设1.Turing Machine
确定性图灵机
图灵机有很多不同的定义#xff0c;这里选取其中一种#xff0c;其它定义下的图灵机往往与下面这种定义的图灵机计算能力等价。
图灵机是一个在一条可双向无限延伸且被划分为若干格子的纸带上进行操作的机器#xff0c;其有内部状态#…1.Turing Machine
确定性图灵机
图灵机有很多不同的定义这里选取其中一种其它定义下的图灵机往往与下面这种定义的图灵机计算能力等价。
图灵机是一个在一条可双向无限延伸且被划分为若干格子的纸带上进行操作的机器其有内部状态还有一个可以在纸带上进行修改与移动的磁针。 图灵机从初始状态与纸带起点起每次根据当前的内部状态和当前磁针指向的纸带上的单元格中的字符进行操作若转移函数没有定义则停机否则根据转移函数将内部状态和磁针指向的格子中的字符进行修改根据L/R决定向左移动一格或向右移动一格。
图灵机与冯·诺依曼计算机解决问题的时间复杂度差别在多项式级别内所以研究复杂度类时可以使用图灵机作为计算模型。
非确定性图灵机
非确定型图灵机是图灵机的一种它与确定型图灵机的不同在于确定型图灵机的每一步只能转移到一个状态而非确定型图灵机可以「同时」转移到多个状态从而在多个「分支」并行计算一旦这些「分支」中有一个在接受状态停机则此非确定性图灵机接受这个输入。
事实上任何确定型图灵机都可以用类似于迭代加深搜索的方式在指数级时间内模拟一台非确定型图灵机多项式时间内的行为。
在现实生活中确定型图灵机相当于单核处理器只支持串行处理而非确定型图灵机相当于理想的多核处理器支持无限大小的并行处理。 在计算过程中机器可以在 多种可能的转移中选择一种继续进行。它的转移函数具有如下形式 图灵可识别当且仅当可用非确定性图灵机识别 模拟过程 输入带 1 包含输入 w 模拟带 2 和地址带 3 都是空的 输入带 1 复制到模拟带 2 上 在模拟带 2 上模拟该分支上的确定性计算 多带图灵机
标准的图灵机只能在一条纸带上进行操作但为了方便本文中研究多带图灵机。对于一个k带图灵机其中一条纸带是只读的输入带而剩下的k-1条纸带可以进行读写并且这条纸带中还有一条纸带用作输出。
多带图灵机的纸带数必须是有限的。
对于一个多带图灵机它使用的空间是磁头在除输入带外的其它纸带上所访问过的单元格数目。 单带上放入 # w 1 w 2 …w n # ⌴ # ⌴ # … # 根据 多带图灵机 的状态转移函数 1. 模拟读取 从左端点的第一个 # 开始扫描 直到第k 1 个 # 确定带点的符号的位置读 取每个带子的内容 2. 模拟移动 移动带点符号的位置用带点版本的某一符号替换普通符号 3. 模拟写入 移动到某个 # 上写下指定符号并把这个位置以右的所有内容向右平移一格 重新写上 # 。 图灵 可识别 当且仅当可用 多带 图灵机识别 丘奇 - 图灵论题 丘奇 - 图灵论题称若一类问题有一个有效的方法解决则这类问题可以被某个图灵机解决。 其中「有效的方法」需要满足 包含有限条清晰的指令当用其解决这类问题的其中一个时这个方法需要在有限步骤内结束且得到正确的答案。 这个论题没有被证明但其是计算理论的一条基本公理。 2.可判定性和可归约性 语言与可判定 【定义】语言 若 集合 A 为包含了所有能被机器 M 接受 的字符串则称字符串集合A 是 机器 M 的 语言 记作 L ( M ) A 又称M 识别 A 或 M 接受 A 。 【定义】可判定 如果一个语言能被某一 判定器 处处停机的图灵机 识别 简称 可判定的 可计算性 不可计算问题 对于一个判定问题若存在一个总是在有限步内停机且能够正确进行判定的图灵机则这个问题是一个 图灵可计算 的问题否则这个问题是一个 图灵不可计算 的问题。 由于图灵机可以被自然数编码所以图灵机的个数是可数无穷而语言即二进制串的集合的个数是不可数无穷而每个图灵机最多判定一个语言所以一定存在图灵不可计算的问题。 停机问题 停机问题是一个经典的图灵不可计算问题给定 和 判定 在输入为 时是否会在有限步内停机。 证明 可判定问题 不可判定问题
