精华内容
下载资源
问答
  • 这是一个简单的单带图灵机,用C++编写,判定输入是否属于语言:n个0后跟n个1
  • 图灵机模拟器 还没结束... ,更好地在桌面上打开。
  • 一、多个带子的图灵机、 二、证明过程设计、 三、模仿操作、 四、模仿带子排列、 五、模仿读写头操作





    一、多个带子的图灵机



    多个带子的图灵机 指的是 图灵机不止一个带子 , 下图是 3 3 3 个带子的图灵机 , 每条带子有一个对应的读写头 , 总共有 3 3 3 个读写头 , 有 一个状态 , 该状态根据指令进行操作 ;

    在这里插入图片描述

    3 3 3 个带子的图灵机当前所处的状态是 q \rm q q , 三个读头所处的位置分别是 1 , a , b \rm 1 , a , b 1,a,b , 三个带子的图灵机根据指令进行操作 ,

    首先将所处的 状态从 q \rm q q 转换成 p \rm p p 状态 ,

    三个读写头指向的字符需要 同时被擦掉 , 并写入新字符 , 其操作看起来相当于三个图灵机同时进行工作 , 有一种错觉就是三个带子的图灵机的计算能力要超过一个带子的图灵机 ;

    事实上 , 三个带子的图灵机的计算能力 , 等同于 一个带子的图灵机的计算能力 ;





    二、证明过程设计



    证明过程 :

    三个带子的图灵机 , 如果其中两个带子不工作 , 等同于一个带子的图灵机 , 因此 三个带子的图灵机的计算能力 大于等于 一个带子的图灵机的计算能力 ;

    然后证明 三个带子的图灵机的计算能力 不会超过 ( 小于等于 ) 一个带子的图灵机的计算能力 ;

    最终得到 三个带子的图灵机的计算能力 等同于 一个带子的图灵机的计算能力 ;





    三、模仿操作



    给定一个 三个带子的图灵机 , 一定能找到一个 一个带子的图灵机 , 可以模仿作出三个带子图灵机相同的计算任务 ;

    相同的计算任务的含义就是 两个 图灵机 接受的语言是相同的 ;


    使用 一个带子图灵机 模仿 三个带子图灵机 ;

    设计 单个带子图灵机 指令集 , 模仿 三个带子图灵机 计算过程 ;





    四、模仿带子排列



    带子的字符排列 :

    三个带子图灵机 一步计算中 , 修改了一次状态 , 同时读写头修改了 3 3 3 次字符 ;

    一个带子图灵机 模仿 三个带子图灵机 上述 一步计算 , 在一个带子图灵机中 , 引入特殊字符 # ,

    1 1 1 个 # 与第 2 2 2 个 # 之间的内容是 1 1 1 个带子的内容 ,

    2 2 2 个 # 与第 3 3 3 个 # 之间的内容是 2 2 2 个带子的内容 ,

    3 3 3 个 # 与第 4 4 4 个 # 之间的内容是 3 3 3 个带子的内容 ;

    上述 1 1 1 个带子 可以模仿 3 3 3 个带子的内容 ;

    特殊字符 # 之间的空间很大 , 可能间隔十几个到几十个字符 , 依次排列即可 ;

    排列顺序如下 : # 1 1 1 个带子的字符串 # 2 2 2 个带子的字符串 # 3 3 3 个带子的字符串 #





    五、模仿读写头操作



    读写头操作 :

    1 1 1 个读写头 模仿 3 3 3 个读写头 操作 :

    1 1 1 个读写头 读写了 第 1 1 1 个带子的字符串 ,

    其并不知道第 2 2 2 个读写头的位置 , 根据字符 a \rm a a 是不能区分当前的读写头位置 , 第 2 2 2 个带子的字符串 中有多个 a \rm a a 字符 ;

    在字符集中 引入 特殊字符 , 如下图中 第 1 1 1 个带子的字符串换中 红色的 1 1 1 与 黑色的 1 1 1 是不同的字符 , 这两个颜色 1 1 1 有公共的部分 , 在指令集中 , 这两个 1 1 1 所起的作用是一样的 ;

    红色的 1 1 1 标志的是读写头所在的位置 , 使用红色表示当前读写头的位置信息 ;

    在这里插入图片描述

    上图中红色的 1 1 1 指的是第一个读写头指向的字符 , 读写完毕后 , 继续向右走 , 走到第二个读写头指向的红色的 a \rm a a 位置 , 然后以此类推 ;

    靠不同的字体颜色 区分出 不同的带子 对应的 读写头指向的字符 , 这样就可以实现 1 1 1 个带子模拟多个带子的图灵机 ;

    使用 1 1 1 个带子的图灵机 模拟 3 3 3 个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟 3 3 3 个带子的图灵机 一步的计算 ;

    展开全文
  • 一、确定性模型的计算复杂性关系、 二、证明 "多个带子图灵机时间复杂度





    一、确定性模型的计算复杂性关系



    计算的 复杂性 取决于 模型的计算 ;


    给定一个函数 t ( n ) \rm t(n) t(n) , 假设有一个 两个带子图灵机 时间复杂度是 O ( t ( n ) ) \rm O(t(n)) O(t(n)) , 那么对应的有相同计算能力的 一个带子图灵机 时间复杂度是 O ( t 2 ( n ) ) \rm O(t^2(n)) O(t2(n)) ;


    示例 : 参考上一篇博客 【计算理论】计算复杂性 ( 两个带子的图灵机的时间复杂度 ) , 识别语言 A = { 0 k 1 k : k ≥ 0 } \rm A = \{ 0^k1^k : k \geq 0 \} A={0k1k:k0} , 一个带子图灵机识别上述语言的 计算时间复杂度是 O ( n 2 ) \rm O(n^2) O(n2) , 两个带子图灵机识别上述语言的 计算时间复杂度是 O ( n ) \rm O(n) O(n) ;





    二、证明 "多个带子图灵机时间复杂度是 O ( n 2 ) \rm O(n^2) O(n2)"



    参考 【计算理论】图灵机 ( 多个带子的图灵机 | 计算能力对比 | 证明过程 | 一个带子图灵机 ) 博客 , 以如下三个带子的图灵机为例 , 加入下面的 三个带子图灵机的时间复杂度是 t ( n ) \rm t(n) t(n) ;

    在这里插入图片描述

    使用 单个带子图灵机 模仿上述 三个带子图灵机 , 那么对应的单个带子图灵机的时间复杂度是 t 2 ( n ) \rm t^2(n) t2(n) ;

    计算 单个单子图灵机 模仿 三个带子图灵机 一步的计算 , 需要花费的步数 ;

    模仿的核心是将三个带子的字符串放在一个带子中 , 使用 “#” 分割 , 并使用红色记录三个带子对应的位置 , 一个读头需要记录三个位置 , 如下图 :

    在这里插入图片描述

    使用 1 1 1 个带子的图灵机 模拟 3 3 3 个带子的图灵机 的代价是 读写头必须从左向右整个遍历一遍带子 , 才能模拟 3 3 3 个带子的图灵机 一步的计算 ;

    最坏的情况下就是 , 三个带子图灵机走 1 1 1 步 , 单个带子图灵机走 三个带子所有字符串的内容长度 对应的步数 , 也就是 10 + 4 10 + 4 10+4 步 , 多出来的 4 4 4 步是 4 4 4 个 “#” 分割字符 ;


    三个带子图灵机 每个带子的长度是 t ( n ) \rm t(n) t(n) , 单个带子图灵机 带子长度是 3 t ( n ) \rm 3t(n) 3t(n) ;

    单个带子图灵机 模仿 三个带子图灵机 一步操作 , 最坏的情况下 , 需要执行的步数是 3 t ( n ) \rm 3t(n) 3t(n) ;

    总共需要模仿 t ( n ) \rm t(n) t(n) 步 , 因此总共需要模仿的步数是 3 t 2 ( n ) \rm 3t^2(n) 3t2(n) ;


    如果是 四个带子图灵机 , 总共需要模仿的步数是 4 t 2 ( n ) \rm 4t^2(n) 4t2(n) ,

    如果是 五个带子图灵机 , 总共需要模仿的步数是 5 t 2 ( n ) \rm 5t^2(n) 5t2(n) ,

    如果是 一百个带子图灵机 , 总共需要模仿的步数是 100 t 2 ( n ) \rm 100t^2(n) 100t2(n) ,

    其数量级还是 t 2 ( n ) \rm t^2(n) t2(n) ,

    因此增加到 2 2 2 个带子 , 与 增加到 100 100 100 个带子 , 甚至 一亿个带子 , 算法复杂度的数量级是 O ( n 2 ) \rm O(n^2) O(n2) , 这是不变的 ;


    单个带子模仿多个带子图灵机 , 所花费的时间是平方增加 , 不管多个带子的个数是多少 ;

    展开全文
  • 图灵机

    千次阅读 2015-03-11 08:56:32
    二、单带图灵机的定义:TM M为一个七元组(有穷状态集、输入字母表、带字母表(通常比输入字母表大、因为还包括可以写上去的字符)、转移函数(需标明向左还是向右)、初始状态、停机接收状态、停机拒绝状态)。...

    一、图灵机的一些特点:双向读写(注意DFA和PDA只是可读,而图灵机可读写)头、无穷带、停机状态。

    二、单带图灵机的定义:TM M为一个七元组(有穷状态集、输入字母表、带字母表(通常比输入字母表大、因为还包括可以写上去的字符)、转移函数(需标明向左还是向右)、初始状态、停机接收状态、停机拒绝状态)。注意一个状态不能同时为接受状态和拒绝状态,所以一个TM至少有两个状态。输入带上除了输入串之外的地方都是空。

    三、单带图灵机的格局,将状态嵌入序列。例如:uqav表示: 当前状态: q, 当前带内容: uav, 当前扫描符号: a。

    初始格局: q0w, w是输入串
    接受格局: u qacc av,
    拒绝格局: u qrej av,
    停机格局: u qacc av, u qrej av, 

    四、格局的转变:C1产生C2: 如果转移(qi,b)=(qj,c,L), 则格局ua qi bv 产生 u qj acv,而qi bv 产生 qj cv (在带左端不能向左移)

    五、1、图灵可识别: A=L(M)。x∈A时, M在x上停机接受;x∉A时, M在x上停机拒绝或不停机(补图灵可识别:x∈A时, M在x上停机接受或不停机;x∉A时, M在x上停机拒绝)
           2、图灵可判定: A=L(M)。x∈A时, M在x上停机接受;x∉A时, M在x上停机拒绝(即处处停机,标明任意输入串x总能够使图灵机停机)

    图灵可识别语言类和图灵可判定语言类对正则运算和补运算封闭。

    六、图灵机判定语言的例子:

    1、A={A是由2的n次幂个0组成的串,n≥0}。主要思路:1、从左向右扫描带子, 隔一个消去一个0;2、若第一步之后, 带子上只剩下1个0, 则接受。3、若第一步之后, 带子上剩下1个以上奇数个0, 则拒绝。4、让读写头返回到带子最左端。5、转到第一步。

    2、B={ w#w | w∈{0,1}* }。思路:1、扫描输入,确认只含一个#,否则拒绝。2、在#两边对应位置来回移动,检查是否含相同符号。若不是,则拒绝。消去已检查过符号。3、当消去#左边所有符号时,检查#右边是否还有符号,若是,则拒绝. 否则接受。

    3、C={ aibjck | i*j=k }。思路:1、从左向右扫描输入, 确认输入具有形式a*b*c*, 否则拒绝。2、让读写头回到带子左端。3、消去1个a, 向右扫描直到b出现。在b和c之间来回移动, 成对消去b和c, 直到消去所有b(若过程中c不够了则拒绝)。4、若还有a未消去, 则恢复所有已消去的b, 重复第三步;若所有a已消去, 则检查是否消去所有c, 若是则接受, 否则拒绝.

    七、发现带左端的技巧:当前位置上写下某个特殊符号,在控制中记住所取代的符号,让带头向左移动。若带头还在特殊符号上,则已经到带子左端;否则,恢复右边的符号, 再向左移。

    八、图灵机的等价变形:双向无穷带、多维带、多带、多头、非确定型……。所以TM概念有很强的稳健性。

    关于多带模拟证明:将多带放到一个带上即可,多带中间用特殊符号隔开,然后每次移动通过寻找特殊符号来界定多带;如果某次移动到了特殊符号,就在这个位置写下空白符,
    并把这个位置以右的所有内容向右平移一格。然后继续模拟。

    关于非确定型的证明:通过遍历(只能用宽搜,深搜的话如果图灵机不停机则出现错误)NTM的计算树。用3个带来模拟:输入带(输入序列)、模拟带(用来模拟当前次)、路径带(指示当前模拟的是计算树上的哪个分支)。

    九、计算装置的几种工作方式:
    识别器: 输入x, 输出 0/1/?(分别表示拒绝、接受和不停机)
    判定器: 输入x, 输出 0/1
    转换器: 输入x, 输出y
    产生器: 输入0n, 输出xn
    枚举器: 输入为空, 输出x1,x2,x3,…无遗漏, 无多余(可重复), 无顺序

    定理;图灵可识别当且仅当图灵可枚举。可识别推出可枚举: 枚举字母表上的串, 逐个识别。通过楔形过程: 对s1,s2,…,sk运行k步(注意不能运行完si再运行si+1,因为si可能不停机,那么字典序大于si的就不能枚举出来了)。可识别推出可枚举: 枚举, 等待x出现。

    十、算法一词的来源及相关历史。来源于9世纪数学家al-Khowarizmi,“from the town of Kowarzimi”,该地现在是 Khiva, Uzbekistan(乌兹别克斯坦)。他的著作《复原和化简的规则》(Kitab al-jabr w’al muquabala)。Algebra一词也源自此书。18世纪出现Algorithm一词,原意阿拉伯数字十进制算术Algorism 。

    1900年, 希尔伯特提出23个问题,希尔伯特第10问题: 有没有求多项式整数根的算法?即“通过有限多次运算就可以决定的过程”。

    Godel不完备性定理: 任何形式系统要么是不完备的(指有定理不能通过这个系统进行证明), 要么是不相容的(系统中有内容是矛盾的)。通过一句话悖论表述:“这句话没有证明”
    算法是直觉概念,他和处处停机图灵机、lambda演算、0型文法 等价(后者都是数学概念,且彼此等价)

    展开全文
  • 一、图灵机图示、 二、图灵机形式定义





    一、图灵机图示



    下图是图灵机的简单示意图 : 图灵机由 无穷长的带子 , 读头 , 状态 组成 ;

    在这里插入图片描述

    带子 :

    无穷长度 , 每个格子有一个字符 ;


    读头 :

    上图中的箭头是读头 , 用于读写数据 ;

    读头作用是 读取带子上的字符 , 然后擦掉该字符 , 写入新的字符 ;

    然后该读头可以 向左或向右移动一格单位 ;


    状态 :

    箭头上的矩形框中表示当前的状态 , 状态个数是有限多个 , 其作用是指挥图灵机如何进行计算 ;


    上述图灵机是理想的图灵机 , 带子是无穷长的 , 带子上的字符是有限多个 , 状态是有限多个 , 指令也是有限多个 ;





    二、图灵机形式定义



    图灵机要素 :

    有限多状态集 , Q \rm Q Q ;

    有限多个字符集 , Σ \rm \Sigma Σ ;

    带子字符集 , Γ \rm \Gamma Γ , 包含 Σ \rm \Sigma Σ ;

    转换函数 , 即指令集 , δ \delta δ ;

    开始状态 , q 0 \rm q_0 q0 , 包含在 Q \rm Q Q 中 ;

    空白字符 , u \rm u u , 包含在 Γ − Σ \rm \Gamma - \Sigma ΓΣ ( 相对补集 ) 集合中 ;

    一些接受状态 , F \rm F F , 其中 F ⊆ Q \rm F \subseteq Q FQ ;


    指令与转换函数 : 图灵机是根据指令进行计算的 , 指令 是一个 转换函数 δ \rm \delta δ ;

    转换函数 δ \rm \delta δ 两个输入参数 :

    • 参数一 : 状态 q \rm q q , 该状态是 Q \rm Q Q 中的元素 , q ∈ Q q \in\rm Q qQ ;
    • 参数二 : 带子字符 Z Z Z , 该字符是 Γ \rm \Gamma Γ 集合中的元素 , Z ∈ Γ \rm Z \in \Gamma ZΓ ;

    转换函数 δ \rm \delta δ 输出是一个三元组 :

    • 输出一 : 状态 p \rm p p ;
    • 输出二 : 带子字符 Y \rm Y Y ;
    • 输出三 : 方向 D \rm D D , 向左或向右 , 读取头下面要移动的方向 ;

    指令 δ \rm \delta δ 表示的含义解析 :

    δ ( q , Z ) = ( p , Y , D ) \rm \delta(q, Z) = (p, Y, D) δ(q,Z)=(p,Y,D) 转换函数 , 其中 q , Z \rm q,Z q,Z 是两个输入 , p , Y , D \rm p, Y, D p,Y,D 是三个输出 ,

    开始时图灵机的 状态是 q \rm q q 状态 , 读取头指向的字符是 Z \rm Z Z ,

    执行该转换函数 δ \rm \delta δ , 会将 状态转变为 p \rm p p 状态 , 将 读取头指向的带子上的字符 Z \rm Z Z 擦除 , 并改为 Y \rm Y Y , 然后 沿着 D \rm D D 方向 , 移动一格单位 ;

    其中 D \rm D D 方向可以是 L \rm L L 向左移动 , 也可以是 R \rm R R 向右移动 ;

    展开全文
  • 一、非确定性图灵机 与 计算树、 二、非确定性、 三、非确定性图灵机 与 确定性图灵机 相互模仿、 四、非确定性图灵机 -> 确定性图灵机
  • 一、图灵机示例、 二、图灵机示例 2
  • 【计算理论】图灵机 ( 图灵机设计 )

    千次阅读 2020-12-04 10:07:22
    一、设计图灵机要求、 二、图灵机分析、 三、计算过程分析、 四、高级语言、 五、使用高级语言描述图灵机、 六、完整图灵机 ( 仅做参考 )
  • 一、接受状态作用、 二、格局、 三、图灵机语言、 四、图灵机设计复杂性、
  • tmsim-图灵机 该项目是基于Web的Turing Machine。 它能够解释用于机器的预定义语言,进行编译和执行。 处理语法错误 该工具能够保存语法错误,并以该错误结束和返回行,并且通常提供其类型的描述。 语义分析 检查...
  • 图灵机模拟器 确定性图灵机 图灵机模拟器,它接受字符串并根据一组给定的转换对其进行处理。 非确定性图灵机 一种非确定性的图林机器的实现,该机器基于给定的过渡集来接受或拒绝字符串。 与确定性图灵机相反,在不...
  • 图灵机简介

    万次阅读 2017-10-19 23:57:05
    今天计算机病毒课上老师给我们介绍了一下图灵机。以前一直有听说过图灵机,今天简单地了解了一下图灵机,写下一些学习过程中的收获。图灵机是由图灵大神由1936年提出的一种确定的抽象计算模型,据说它可以被看做是...
  • 图灵机探索

    2021-06-12 22:48:54
    图灵机是阿兰图灵在解决可计算数判定性问题时,提出的一种解决方法,图灵在论文中使用到了该计算机器。 刨去图灵机的分类和形式化的定义,图灵机执行一系列的状态变化。把只包含0和1的字符串输入到图灵机中,图灵...
  • 你深入理解图灵机--什么是图灵机、图灵完备

    千次阅读 多人点赞 2019-06-27 03:22:13
    我们知道图灵机首次提出在图灵的一篇论文《论数字计算在决断难题中的应用》中提出,原论文题目为《On Computable Numbers, with an Appl...
  • 图灵机.pdf

    2011-11-06 11:28:46
    图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf 图灵机.pdf
  • 两个带子的图灵机的时间复杂度

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,804
精华内容 11,921
关键字:

单带图灵机