美文网首页
Problems of Turing machines

Problems of Turing machines

作者: richybai | 来源:发表于2022-03-17 11:33 被阅读0次
1.3 The halting problem is undecidabel. 请证明对于给定的图灵机和输入，没有算法能决定图灵机对这个输入是否停止。

证明：假设有通用图灵机U
U([M], x)=\left\{ \begin{array}{ll} \text{yes, if }M(x) \text{=stop} \\ \text{no, otherwise} \end{array} \right.
我们定义图灵机U'来模仿U
U'(y)=\left\{ \begin{array}{ll} \text{not stop, if }U(y,y)=\text{yes} \\ \text{stop, if }U(y,y)=\text{no} \end{array} \right.
现在考虑U'([U']):

  1. 假设U'([U']) = \text{stop}，则U([U'],[U']) = \text{no}，即U'([U'])=\text{not stop}，矛盾。
  2. 假设U'([U']) = \text{not stop}，则U([U'],[U']) = \text{yes}，即U'([U'])=\text{stop}，矛盾。

定义enumeration：如果集合X \subseteq A^*由一个图灵机E的所有可能的输出构成，则称它是可以枚举的(enumerable)。
非正式的说，就是可以把元素一个一个拿出来。

1.4 证明没有算法可以枚举(enumerate)所有没有输入且不停机的图灵机。

证明： pass。

Extending TM
multi-tape turing machine: 展示网页
多纸带图灵机运行的时候，状态转换函数把所有纸带的符号都考虑了进去。多纸带可以运行的更快，但和单纸带图灵机的区别并没有很大。

1.6 证明当输入长度为n时，运行时长为T(n)的2-tape图灵机可以由运行时长为O(T^2(n))的1-tape图灵机模拟。
1.7 证明当输入长度为n时，运行时长为T(n)的3-tape图灵机可以由运行时长为O(T^2(n)\log T(n))的2-tape图灵机模拟。

总之，运行时长为T(n)的k-tape图灵机可以由运行时长为O(T^2(n))的1-tape图灵机模拟

相关文章

网友评论

      本文标题：Problems of Turing machines

      本文链接：https://www.haomeiwen.com/subject/cohvdrtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Problems of Turing machines|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！