1

Arthur Dent 使用地球上尚不可用的太空时代技术开发了一种算法,该算法可确定 TM M1 在空白磁带上启动时是否停止。但后来,他发现生命、宇宙和一切的意义是42。

(a) [5] 给定一个 TM M2,证明 Arthur 可以使用他已经开发的程序确定 M2 在输入 42 上是否停止,该程序确定 TM M1 在空白磁带上启动时是否停止。如果您在证明中创建了一个新 TM,请给出其机器模式。

(b) [5] 假设有一个程序比 Arthur 的程序快,但它回答了 TM M2 是否在输入 42 上停止的问题。解释 Arthur 如何使用该算法来确定某个 TM M1 在空白处启动时是否停止胶带。如果您在证明中创建了一个新 TM,请给出其机器模式。

(c) [5] 我们在课堂上证明了确定 TM M 在空白磁带上启动时是否停止的问题是不可判定的。是 (a) 部分还是 (b) 部分可以用来证明确定 TM M 是否在输入 42 上停止也是不可判定的?

任何人都可以帮我破译我的教授在这里所说的内容吗?

4

1 回答 1

2

欢迎来到一些非常复杂的计算机科学理论。尝试从这里开始:http ://en.wikipedia.org/wiki/Halting_problem

如果你不熟悉的话,谷歌图灵机也是如此。

于 2010-12-07T04:18:30.040 回答