图灵机的定义说禁止读取/修改它的指令表（程序）。确切地说，图灵机无法访问它自己的程序。
如果可以削弱这种限制，可以带来什么好处？如果一台机器可以分析和/或修改它的程序。这会扩展图灵可计算任务的类别吗？
问问题
892 次
2 回答
5
图灵机已经可以实现另一个图灵机，并改变它的规则，比如说，将一个可修改的程序作为输入。特别是，图灵机可以计算任何可计算的函数。理论上它可以实现一个 lisp 解释器，它有宏、“自修改”代码等。
所以，答案是否定的。请记住，没有人，而且我的意思是绝对没有人真正想要一台图灵机，尽管毫无疑问已经编写了无数的模拟器。（我不会承认，但作为一名本科生，我可能做过类似的事情......）这只是各种重要证明的基础。
于 2009-10-08T04:35:04.150 回答
2
更完整地说：“通用图灵机”和“图灵机”之间存在差异。普通图灵机具有硬连线规则集，因此无法自行修改。您描述的是通用图灵机，它从用于 I/O 的同一磁带中读取其规则集，并能够修改该规则集。如果 UTM 能够从磁带重新加载（重新启动）修改后的规则集，那么它实际上已经是自己的了-修改。
于 2012-03-31T18:25:06.617 回答