 |
|
|
Halting problem - Sketch of proof | A Wisdom Archive on Halting problem - Sketch of proof | | Halting problem - Sketch of proof A selection of articles related to Halting problem - Sketch of proof | |
|
|
More material related to Halting Problem can be found here:
|
|
|
| | |
Halting problem, Halting problem - Can humans solve the halting problem?, Halting problem - Common pitfalls, Halting problem - Footnotes, Halting problem - Formal statement, Halting problem - Formalization of the halting problem, Halting problem - History of the Halting Problem, Halting problem - Importance and consequences, Halting problem - Recognizing partial solutions, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Sketch of proof
| | |
|
ARTICLES RELATED TO Halting problem - Sketch of proof | | | |  Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Sketch of proofThe proof proceeds by reductio ad absurdum. We start with assuming that there is a function halt(a, i) that returns true if the algorithm represented by the string a halts when given as input the string i, and returns false otherwise. (The existence of the universal Turing machine proves that every possible algorithm corresponds to at least one such string.) Given this algorithm we can construct another algorithm trouble(s) as follows:
function trouble(string s)
if halt(s, s) = false
r ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Sketch of proof |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - History of the Halting Problem In the following: H refers to the source "Hodges" U refers to the source "Undecidable" W refers to definitions from Websters Ninth New Collegiate Dictionary Marriam-Webster Inc., Springfield Mass, 1990 PM refers to the source Principia Mathematica
circa B.C.-- Pythagoras shows the existence of numbers that are not rational, i.e. numbers exist that are not the natural numbers or ratios of the counting numbers. Numbers that are either natural numbers or ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - History of the Halting Problem |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Can humans solve the halting problem? It might seem like humans could solve the halting problem. After all, a programmer can often look at a program and tell whether it will halt. It is useful to understand why this cannot be true. For simplicity, we will consider the halting problem for programs with no input, which is also undecidable.
To "solve" the halting problem means to be able to look at any program and tell whether it halts. It is not enough to be able to look at some programs and decide. Humans may also not be able to solve the halting problem, due ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Can humans solve the halting problem? |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Relationship with Gödel's incompleteness theorem The concepts raised by Gödel's incompleteness theorems are very similar to those raised by the halting problem, and the proofs are quite similar. In fact, a weaker form of the First Incompleteness Theorem is an easy consequence of the undecidability of the halting problem. This weaker form differs from the standard statement of the incompleteness theorem by asserting that a complete, consistent and sound axiomatization of all statements about natural numbers is unachievable. The "sound" part is the weakening: it means that we require ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Relationship with Gödel's incompleteness theorem |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Recognizing partial solutions No program can solve the halting problem. There are programs that give correct answers for some instances of it, and run forever on all other instances. A program that returns answers for some instances of the halting problem might be called a partial halting solver (PHS). Can we recognize a correct PHS when we see it? Let the PHS recognition problem be this: given a PHS, determine whether it returns only correct answers. This problem sounds like it might be easier than the halting problem itself. It is not. It is ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Recognizing partial solutions |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Formalization of the halting problem In his original proof Turing formalized the concept of algorithm by introducing Turing machines. However, the result is in no way specific to them; it applies equally to any other model of computation that is equivalent in its computational power to Turing machines, such as Markov algorithms, Lambda calculus, Post systems or register machines.
What is important is that the formalization allows a straightforward mapping of algorithms to some data type that the algorithm can operate upon. For example, if the formalism lets algori ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Formalization of the halting problem |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Importance and consequences The importance of the halting problem lies in the fact that it is the first problem to be proved undecidable. Subsequently, many other such problems have been described; the typical method of proving a problem to be undecidable is with the technique of reduction. To do this, the computer scientist shows that if a solution to the new problem was found, it could be used to decide an undecidable problem (by transforming instances of the undecidable problem into instances of the new problem). Since we already know that no method can decid ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Importance and consequences |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Common pitfalls Many students, upon analyzing the above proof, ask whether there might be an algorithm that can return a third option, such as "undecidable." This reflects a misunderstanding of decidability. It is easy to construct one algorithm that always answers "halts" and another that always answers "doesn't halt." For any specific program and input, one of these two algorithms answers correctly, even though nobody may know which one. The difficulty of the halting problem lies not in particular programs, but in the requ ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Common pitfalls |
| |
|
| | | | Halting problem - Sketch of proof: Encyclopedia II - Halting problem - Formal statement One possible way of formally stating the halting problem is as follows:
Given a Gödel numbering of the computable functions,
with the Cantor pairing function,
the set is called the halting set.
The problem of deciding whether the halting set is recursive or not is called the halting problem. As the set is recursively enumerable the halting problem is not solvable by a computable function.
Alternative equivalent formulations, for inst ...
See also:Halting problem, Halting problem - Formal statement, Halting problem - Importance and consequences, Halting problem - Sketch of proof, Halting problem - Common pitfalls, Halting problem - Formalization of the halting problem, Halting problem - Relationship with Gödel's incompleteness theorem, Halting problem - Can humans solve the halting problem?, Halting problem - Recognizing partial solutions, Halting problem - History of the Halting Problem, Halting problem - Footnotes Read more here: » Halting problem: Encyclopedia II - Halting problem - Formal statement |
| |
|
| |
|
|
|
|
More material related to Halting Problem can be found here:
|
|
|
|
| |
