49
个编辑
更改
跳到导航
跳到搜索
第10行：
第10行： − + 第17行：
第17行： + + + 第467行：
第470行： − + − halts on arbitrary input ''x''; that is, the following function ''h'' is not computable (Penrose 1990, p. 57–63):+
无编辑摘要
在可计算性理论中，停机问题是从任意一个计算机程序的描述和一个输入来确定程序是否会完成运行，或者永远继续运行。阿兰 · 图灵在1936年证明了解决所有可能的程序输入对的停机问题的一般算法是不存在的。
在可计算性理论中，停机问题是从任意一个计算机程序的描述和一个输入来确定程序是否会完成运行，或者永远继续运行。阿兰 · 图灵在1936年证明了解决所有可能的程序输入对的停机问题的一般算法是不存在的。
【最终版】在可计算性理论中，停机问题是指从对任意计算机程序和输入的描述中确定程序是否将结束运行，或继续永远运行的问题。艾伦·图灵在1936年证明，解决所有可能的程序输入对停机问题的通用算法是不存在的。
For any program ''f'' that might determine if programs halt, a "pathological" program ''g'', called with some input, can pass its own source and its input to ''f'' and then specifically do the opposite of what ''f'' predicts ''g'' will do. No ''f'' can exist that handles this case. A key part of the proof is a mathematical definition of a computer and program, which is known as a [[Turing machine]]; the halting problem is ''[[Undecidable problem|undecidable]]'' over Turing machines. It is one of the first cases of [[decision problem]]s proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.
For any program ''f'' that might determine if programs halt, a "pathological" program ''g'', called with some input, can pass its own source and its input to ''f'' and then specifically do the opposite of what ''f'' predicts ''g'' will do. No ''f'' can exist that handles this case. A key part of the proof is a mathematical definition of a computer and program, which is known as a [[Turing machine]]; the halting problem is ''[[Undecidable problem|undecidable]]'' over Turing machines. It is one of the first cases of [[decision problem]]s proven to be unsolvable. This proof is significant to practical computing efforts, defining a class of applications which no programming invention can possibly perform perfectly.
对于任何可能决定程序是否停止的程序，一个“病态的”程序 g，带有一些输入，可以将它自己的源和输入传递给 f，然后具体地做与 f 预测的相反的事情。没有 f 可以处理这种情况。证明的一个关键部分是计算机和程序的数学定义，也就是所谓的图灵机; 停机问题在图灵机上是不可判定的。这是决策问题被证明无法解决的首批案例之一。这一证明对实际计算工作具有重要意义，它定义了一类任何编程发明都不可能完美执行的应用程序。
对于任何可能决定程序是否停止的程序，一个“病态的”程序 g，带有一些输入，可以将它自己的源和输入传递给 f，然后具体地做与 f 预测的相反的事情。没有 f 可以处理这种情况。证明的一个关键部分是计算机和程序的数学定义，也就是所谓的图灵机; 停机问题在图灵机上是不可判定的。这是决策问题被证明无法解决的首批案例之一。这一证明对实际计算工作具有重要意义，它定义了一类任何编程发明都不可能完美执行的应用程序。
【最终版】对于任何可能决定程序是否停止的程序f，一个“病态的”程序g，通过一些输入调用，可以将它自己的源和输入传递给f，然后特别地做f预测g将做的相反的事情。没有f可以处理这种情况。证明的关键部分是计算机和程序的数学定义，这被称为图灵机;在图灵机上，停机问题是无法确定的。这是首批被证明无法解决的决策问题之一。这个证明对于实际的计算工作是很重要的，它定义了任何编程发明都不可能完美执行的一类应用程序。
|- style="font-size:9pt; text-align:center; background:#f2f2f2;"
|- style="font-size:9pt; text-align:center; background:#f2f2f2;"
|-style = “ font-size: 9 pt; text-align: center; background: # f2f2f2; ”
|-style = “ font-size: 9 pt; text-align: center; background: # f2f2f2; ”
; that is, the following function ''h'' is not computable (Penrose 1990, p. 57–63):
| style="background:#f2f2f2; width:24.75;"| 1
| style="background:#f2f2f2; width:24.75;"| 1