更改
→图灵停机问题
我们将一个程序X作用到它自身的源代码x这个特殊的事件编码为"X(x)",并定义一个叫做蒯恩的计算机程序产生这样的编码,也就是定义:
我们将一个程序X作用到它自身的源代码x这个特殊的事件编码为"X(x)",并定义一个叫做蒯恩的计算机程序产生这样的编码,也就是定义:
<math>Q(x):=''X(x)''</math>;
<div style="text-align: center;"><math>Q(x):=''X(x)''</math>;</div>
那么,最终的判断H(z,z)又可以写成:H(Q(z))。所以实际上,D程序的第一部分就是将判断停机的函数H和蒯恩函数Q放到一起并同时作用到代码z上面。
那么,最终的判断H(z,z)又可以写成:H(Q(z))。所以实际上,D程序的第一部分就是将判断停机的函数H和蒯恩函数Q放到一起并同时作用到代码z上面。
程序的第二部分则是一个取反的操作,也就是如果H(z,z)判断为yes,程序就进入死循环,如果判断为no,程序就退出。而在证明的最后一步,将D作用到它的源代码d上面会产生什么情景?这个D(d)的操作恰恰能够实现自指悖论。有关图灵停机问题的详细解释请参看:图灵机与计算理论。我们将在下一小节看出这些自指技术的共同之处。
程序的第二部分则是一个取反的操作,也就是如果H(z,z)判断为yes,程序就进入死循环,如果判断为no,程序就退出。而在证明的最后一步,将D作用到它的源代码d上面会产生什么情景?这个D(d)的操作恰恰能够实现自指悖论。有关图灵停机问题的详细解释请参看:[图灵机与计算理论 图灵机与计算理论]。我们将在下一小节看出这些自指技术的共同之处。
====哥德尔定理<sup>2</sup>====
====哥德尔定理<sup>2</sup>====