讨论:停机问题
MS1337在话题“U(P) 的实现不符合定义啊(笑)”中的最新留言:7年前
停机问题属于维基百科数学主题的基础条目第五级。请勇于更新页面以及改进条目。 本条目属于下列维基专题范畴: |
|||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Untitled
不理解对停机问题的证明:
设停机问题有解,即:存在过程H(P, I)可以给出程序P在输入I的情况下是否可停机。假设若P在输入I时可停机,H输出“停机”,反之输出“死循环”,
这个假设有无问题。既是死循环,就说明在一直不停地在计算而没有得到结果,这时怎么让其判定自己是死循环而输出死循环结束自己呢? --Aabbcc001 2007年9月22日 (六) 14:26 (UTC)
- 他是假设存在一个图灵机能够决定此问题,那么建构一个新图灵机基于此图灵机的输出,当此图灵机输出否(死循环)则不改变行为,此图灵机输出是(停止)则执行死循环,也就是说此假设的图灵机本身已经能够在有限的时间中决定他的输入是否会停......Arcanum (留言) 2008年7月10日 (四) 21:55 (UTC)
停机问题和参见里的未解决的数学问题本质上没什么联系吧。 --60.2.23.250 (留言) 2011年7月23日 (六) 11:14 (UTC)
第一段“在使用 oracle 输入的帮助下”似乎是笔误?
U(P) 的实现不符合定义啊(笑)
原文定义如下:
int U(P) {
if (H(P, P) == 1) {
return 0;
} else {
while(1) { }
}
}
燃鹅若进入死循环,返回值便不是 int 了啊……(笑)—以上未签名的留言由Wang Nianyi(对话|贡献)于2017年8月27日 (日) 13:27 (UTC)加入。
仅当返回的时候才返回 int,而进入死循环的时候便不会返回——这个实现是正确的。MS1337(留言) 2017年11月13日 (一) 18:10 (UTC)