图灵机和机器模式
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上停止也是不可判定的？
谁能帮我解读我的教授在这里所说的内容吗？
Arthur Dent, using space age technology not yet available on earth developed an algorithm which determines if a TM M1 halts or not when started on a blank tape. But then later, he discovered that the meaning to life, the universe, and everything is 42.
(a) [5] Given a TM M2, prove that Arthur can determine if M2 halts or not on the input 42 using the program he already developed which determines if a TM M1 halts or not when started on a blank tape. If you create a new TM in your proof, give its machine schema.
(b) [5] Suppose there is a program which is faster than Arthur's but it answers the question of whether a TM M2 halts on input 42. Explain how Arthur can use this algorithm to determine if some TM M1 halts when started on a blank tape. If you create a new TM in your proof, give its machine schema.
(c) [5] We proved in class that that the problem of determining if a TM M halts when started on a blank tape is not decidable. Is it part (a) or part (b) which can be used to prove that it is also undecidable to determine if a TM M halts on input 42?
Can anyone help me decipher what my prof is talking about here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
欢迎来到一些非常复杂的计算机科学理论。尝试从这里开始：http://en.wikipedia.org/wiki/Halting_problem
Google 图灵机作为好吧，如果你对此不熟悉的话。
Welcome to some really complicated computer science theory. Try starting here: http://en.wikipedia.org/wiki/Halting_problem
Google Turing Machine as well if you're not familiar with that.