图灵机说明书

Question

图灵机的定义说，禁止人们阅读/修改其指令表（程序）。确实，图灵机无法访问其自己的程序。

如果可以弱化这一限制，可以获得什么好处？如果机器可以分析和/或修改其程序。这会扩展图灵计算任务的类别吗？

Answer 1

图灵机已经可以实现另一台图灵机，并更改其规则，例如以可修改程序作为输入。特别是，图灵机可以计算任何可计算的函数。从理论上讲，它可以实现一个lisp解释器，该解释器将具有宏，“自我修改”代码等。

因此，答案是否定的。记住，没有人，而且我的意思是绝对没有人在任何地方实际上都想要 Turing机器，尽管无疑已经编写了无数的模拟器。（我不会承认，但是作为一个本科生，我可能会做类似的事情……）这只是各种重要证据的基础。