更改

【最终版】对于任何可能决定程序是否停止的程序f，一个“病态的”程序g，通过一些输入调用，可以将它自己的源和输入传递给f，然后特别地做f预测g将做的相反的事情。没有f可以处理这种情况。证明的关键部分是计算机和程序的数学定义，这被称为图灵机;在图灵机上，停机问题是无法确定的。这是首批被证明无法解决的决策问题之一。这个证明对于实际的计算工作是很重要的，它定义了任何编程发明都不可能完美执行的一类应用程序。

【最终版】对于任何可能决定程序是否停止的程序f，一个“病态的”程序g，通过一些输入调用，可以将它自己的源和输入传递给f，然后特别地做f预测g将做的相反的事情。没有f可以处理这种情况。证明的关键部分是计算机和程序的数学定义，这被称为图灵机;在图灵机上，停机问题是无法确定的。这是首批被证明无法解决的决策问题之一。这个证明对于实际的计算工作是很重要的，它定义了任何编程发明都不可能完美执行的一类应用程序。

[[Jack Copeland]] (2004) attributes the introduction of the term ''halting problem'' to the work of [[Martin Davis (mathematician)|Martin Davis]] in the 1950s.<ref>In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index.  The earliest known use of the words "halting problem" is in a proof by Davis (1958, p.&nbsp;70–71):

[[Jack Copeland]] (2004) attributes the introduction of the term ''halting problem'' to the work of [[Martin Davis (mathematician)|Martin Davis]] in the 1950s.<ref>In none of his work did Turing use the word "halting" or "termination". Turing's biographer Hodges does not have the word "halting" or words "halting problem" in his index.  The earliest known use of the words "halting problem" is in a proof by Davis (1958, p.&nbsp;70–71):

Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952, p.&nbsp;382). Copeland (2004, p 40) states that:

Davis adds no attribution for his proof, so one infers that it is original with him. But Davis has pointed out that a statement of the proof exists informally in Kleene (1952, p.&nbsp;382). Copeland (2004, p 40) states that:

: "The halting problem was so named (and it appears, first stated) by Martin Davis [cf. Copeland footnote 61]... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)."</ref>

:"The halting problem was so named (and it appears, first stated) by Martin Davis [cf. Copeland footnote 61]... (It is often said that Turing stated and proved the halting theorem in 'On Computable Numbers', but strictly this is not true)."</ref>

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long and use an arbitrary amount of storage space before halting. The question is simply whether the given program will ever halt on a particular input.

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long and use an arbitrary amount of storage space before halting. The question is simply whether the given program will ever halt on a particular input.

停机问题是关于固定的图灵完全计算模型上的计算机程序性质的决策问题，也就是说，所有程序都可以用某种给定的编程语言编写，这种编程语言的通用性足以等价于一台图灵机。问题是确定，给定一个程序和程序的一个输入，程序是否最终在运行该输入时停止。在这个抽象的框架中，程序执行所需的内存和时间没有资源限制; 它可以花费任意长的时间，并且在停止之前使用任意数量的存储空间。问题很简单，给定的程序是否会在某个特定的输入上停止。

停机问题是关于固定的图灵完全计算模型上的计算机程序性质的决策问题，也就是说，所有程序都可以用某种给定的编程语言编写，这种编程语言的通用性足以等价于一台图灵机。问题是确定，给定一个程序和程序的一个输入，程序是否最终在运行该输入时停止。在这个抽象的框架中，程序执行所需的内存和时间没有资源限制; 它可以花费任意长的时间，并且在停止之前使用任意数量的存储空间。问题很简单，给定的程序是否会在某个特定的输入上停止。

 

 

== Background ==

== Background ==

For example, in pseudocode, the program

For example, in pseudocode, the program

|-style = “ font-size: 9 pt; text-align: center; background: # f2f2f2; ”

|-style = “ font-size: 9 pt; text-align: center; background: # f2f2f2; ”

| style="background:#f2f2f2; width:24.75;"| 1

| style="background:#f2f2f2; width:24.75;"| 1