“halting problem”的概念、定义、翻译、参考文献-科学参考

halting problem

Computer

A decision problem that was discovered and investigated by Alan Turing in 1936. Suppose M is a Turing machine and let x be an input to M. If we start the machine running two things might happen: after a finite number of steps the machine might stop, or it might run on forever. Is there any way to test, given M and x, which of these two situations will occur? This is the halting problem. In fact there is no algorithm or effective procedure that, given any Turing machine and its input, will decide whether or not the calculation ever terminates.
Assuming the Church-Turing thesis, the halting problem is algorithmically unsolvable or undecidable. It is one example of many unsolvable problems in mathematics and computer science. It has profound practical implications: if it were solvable it would be possible to write a program tester that, given (say) any Pascal program and its input, would print ‘yes’ if the program terminated after a finite number of steps and ‘no’ if it did not. For any programming language that can define the recursive functions, no such termination program exists.

Logic

1. The problem of deciding whether a given Turing machine will halt, granted a set of initial conditions. The halting problem is notable for being undecidable. If a Turing machine does halt on a particular input, this will occur in a finite amount of time but if the Turing machine does not halt, then there is no way to uniformly determine this fact.
2. The set $K$ of natural numbers encoding all pairs $〈 m, n 〉$ such that the $m$ th Turing machine in an enumeration of Turing machines halts on input $n$ . As determining whether an arbitrary Turing machine will halt on an input $n$ is undecidable, determining whether a number $n^{'} \in K$ is likewise undecidable.

Philosophy

The fundamental decision problem in the theory of computation. It is the problem of finding whether there is an effective procedure for telling whether a Turing machine computation ever terminates, for an arbitrary input. The negative solution is that there is no such procedure. So there can be no ‘program tester’ that, given any program and its input, answers the question of whether the program ever terminates.

单词	halting problem
释义	halting problem Computer A decision problem that was discovered and investigated by Alan Turing in 1936. Suppose M is a Turing machine and let x be an input to M. If we start the machine running two things might happen: after a finite number of steps the machine might stop, or it might run on forever. Is there any way to test, given M and x, which of these two situations will occur? This is the halting problem. In fact there is no algorithm or effective procedure that, given any Turing machine and its input, will decide whether or not the calculation ever terminates. Assuming the Church-Turing thesis, the halting problem is algorithmically unsolvable or undecidable. It is one example of many unsolvable problems in mathematics and computer science. It has profound practical implications: if it were solvable it would be possible to write a program tester that, given (say) any Pascal program and its input, would print ‘yes’ if the program terminated after a finite number of steps and ‘no’ if it did not. For any programming language that can define the recursive functions, no such termination program exists. Logic 1. The problem of deciding whether a given Turing machine will halt, granted a set of initial conditions. The halting problem is notable for being undecidable. If a Turing machine does halt on a particular input, this will occur in a finite amount of time but if the Turing machine does not halt, then there is no way to uniformly determine this fact. 2. The set $K$ of natural numbers encoding all pairs $〈 m, n 〉$ such that the $m$ th Turing machine in an enumeration of Turing machines halts on input $n$ . As determining whether an arbitrary Turing machine will halt on an input $n$ is undecidable, determining whether a number $n^{'} \in K$ is likewise undecidable. Philosophy The fundamental decision problem in the theory of computation. It is the problem of finding whether there is an effective procedure for telling whether a Turing machine computation ever terminates, for an arbitrary input. The negative solution is that there is no such procedure. So there can be no ‘program tester’ that, given any program and its input, answers the question of whether the program ever terminates.
随便看	Lehmann, Johann Gottlob (1719–67) Lehmann–Scheffé theorem Lehn, Jean Marie Pierre Leibler, Richard Arthur (1914–2003) Leibniz, Gottfried Wilhelm Leibniz, Gottfried Wilhelm (1646–1716) Leibniz’ law Leibniz’s integral rule Leibniz’s law Leibniz’s Theorem Leicester, Robert Dudley, 1st Earl of Leidenfrost effect Leif Ericsson Leighton–Pendexter classification Leipzig, Battle of Leishman, Sir William Boog Leishman’s stain Leisler, Jacob (1640–91) leisure tellerette telluric anomaly telluric current telluric lines tellurides tellurium