关于停机问题维基百科给出的定义是：
停机问题（halting problem）是逻辑数学中可计算性理论的一个问题。通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序
讯享网和输入
, 程序在输入下是否能够最终停止。
这个问题的结论是一个可以解决停机问题的通用算法是不存在的。问题倒是很好理解，关键在于怎么证明它的结论——很简单，利用两个方法构成一个悖论。
证明如下：
设停机问题有解，即：存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机，H输出“停机”，反之输出“死循环”（就是一直在运行）。
int H(procedure,Input); // 这里的H函数有两种返回值，死循环(1) 或 停机(0) int K(P) { if (H(P,P) == 1){//如果P死循环 return 0; //这里会停机 }else{//如果P停机 while(1){} // 这里会死循环 } } 讯享网
现在假设H的输入为K，则H变为H(K,K)，K的输入为它自己，即K(K)。
- 假设H(K,K)==1，即如果输入K时程序K一直运行，则返回0，表示K停机，产生矛盾。
- 假设H(K,k)!=1，即如果输入K时程序K停机，则执行死循环，表示K一直运行，产生矛盾。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/121119.html