49
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共3473，未经人工整理和审校，带来阅读不便，请见谅。+ − {{more footnotes|date=September 2018}} 第185行：
第184行： − + 第448行：
第447行： − − { | class = “ wikitable” style = “ padding-bottom: 0.5 em; margin-bottom: 0; margin-top: 1em; margin-left: auto; margin-right: auto; ” − − The method used in the proof is called ''diagonalization'' - ''g'' does the opposite of what ''halts'' says ''g'' should do. The difference between this sketch and the actual proof is that in the actual proof, the computable function ''halts'' does not directly take a subroutine as an argument; instead it takes the source code of a program. The actual proof requires additional work to handle this issue. Moreover, the actual proof avoids the direct use of recursion shown in the definition of ''g''. − 第473行：
第467行： − + − + − The concept above shows the general method of the proof; this section will present additional details. The overall goal is to show that there is no [[total function|total]] [[computable function]] that decides whether an arbitrary program ''i'' halts on arbitrary input ''x''; that is, the following function ''h'' is not computable (Penrose 1990, p. 57–63): 第977行：
第970行： − + − − </div > 第1,041行：
第1,032行： − </div> 第1,106行：
第1,096行： − − </div> − − </div >
无编辑摘要
此词条由范星辰翻译。
{{short description|Problem of determining whether a given program will finish running or continue forever}}
{{short description|Problem of determining whether a given program will finish running or continue forever}}
In [[computability theory (computer science)|computability theory]], the '''halting problem''' is the problem of determining, from a description of an arbitrary [[computer program]] and an input, whether the program will finish running, or continue to run forever. [[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for all possible program-input pairs cannot exist.
In [[computability theory (computer science)|computability theory]], the '''halting problem''' is the problem of determining, from a description of an arbitrary [[computer program]] and an input, whether the program will finish running, or continue to run forever. [[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for all possible program-input pairs cannot exist.
Minsky notes, however, that a computer with a million small parts, each with two states, would have at least 2<sup>1,000,000</sup> possible states:
Minsky notes, however, that a computer with a million small parts, each with two states, would have at least 2<sup>1,000,000</sup> possible states:
然而，明斯基指出，一台有100万个小部件的计算机，每个小部件有两个状态，至少会有2个 < sup > 1,000,000个 </sup > 可能状态:
然而，明斯基指出，一台有100万个小部件的计算机，每个小部件有两个状态，至少会有2个 < sup > 1,000,000个 可能状态:
Sometimes these programmers use some general-purpose (Turing-complete) programming language,
Sometimes these programmers use some general-purpose (Turing-complete) programming language,
{| class="wikitable" style="padding-bottom:0.5em; margin-bottom:0; margin-top:1em; margin-left:auto; margin-right:auto;"
{| class="wikitable" style="padding-bottom:0.5em; margin-bottom:0; margin-top:1em; margin-left:auto; margin-right:auto;"
|- style="font-size:9pt; text-align:center; vertical-align:bottom;"
|- style="font-size:9pt; text-align:center; vertical-align:bottom;"
|- 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; ”
halts on arbitrary input ''x''; 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
<small>Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f(i,i) and g(i) are shown at the bottom; U indicates that the function g is undefined for a particular input value.</small>
<small>Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f(i,i) and g(i) are shown at the bottom; U indicates that the function g is undefined for a particular input value.</small>
2 d 数组排列的总可计算函数 f 的可能值。橙色的单元格是对角线。F (i，i)和 g (i)的值显示在底部; u 表示函数 g 没有为特定的输入值定义。</small >
2 d 数组排列的总可计算函数 f 的可能值。橙色的单元格是对角线。F (i，i)和 g (i)的值显示在底部; u 表示函数 g 没有为特定的输入值定义。
| style="background:#ffc000;"| 0
| style="background:#ffc000;"| 0
</div>
</div>
| style="background:#ffc000;"| 1
| style="background:#ffc000;"| 1
<small>Possible values for a total computable function ''f'' arranged in a 2D array. The orange cells are the diagonal. The values of ''f''(''i'',''i'') and ''g''(''i'') are shown at the bottom; ''U'' indicates that the function ''g'' is undefined for a particular input value.</small>
<small>Possible values for a total computable function ''f'' arranged in a 2D array. The orange cells are the diagonal. The values of ''f''(''i'',''i'') and ''g''(''i'') are shown at the bottom; ''U'' indicates that the function ''g'' is undefined for a particular input value.</small>
* conditional branching (program ''e'' selects between two results depending on the value it computes for ''f''(''i'',''i'')),
* conditional branching (program ''e'' selects between two results depending on the value it computes for ''f''(''i'',''i'')),
* not producing a defined result (for example, by looping forever),
* not producing a defined result (for example, by looping forever),