Halting problem

In computability theory, the halting problem is the decision problem of, given an arbitrary computer program and an input, determining whether said program will eventually finish running and halt, or will continue to run forever. Alan Turing proved in 1937 that the halting problem is undecidable, meaning that no general algorithm exists that can correctly solve the problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine. The proof then shows, for any program that might determine whether programs halt, that a "pathological" program exists for which makes an incorrect determination. Specifically, is the program that, when called with some input, passes its own source and its input to f and does the opposite of what predicts will do. The behavior of on shows undecidability as it means no program will solve the halting problem in every possible case.

In computability theory, the halting problem is the decision problem of, given an arbitrary computer program and an input, determining whether said program will eventually finish running and halt, or will continue to run forever. Alan Turing proved in 1937 that the halting problem is undecidable, meaning that no general algorithm exists that can correctly solve the problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine. The proof then shows, for any program that might determine whether programs halt, that a "pathological" program exists for which makes an incorrect determination. Specifically, is the program that, when called with some input, passes its own source and its input to f and does the opposite of what predicts will do. The behavior of on shows undecidability as it means no program will solve the halting problem in every possible case. ===Timeline=== K = {(i, x) | program i halts when run on input x} represents the halting problem. This set is recursively enumerable, which means there is a computable function that lists all of the pairs (i, x) it contains. However, the complement of this set is not recursively enumerable. def g() -> None: if halts(g): loop_forever() halts(g) must either return true or false, because halts was assumed to be total. If halts(g) returns true, then g will call loop_forever and never halt, which is a contradiction. If halts(g) returns false, then g will halt, because it will not call loop_forever; this is also a contradiction. Overall, g does the opposite of what halts says g should do, so halts(g) can not return a truth value that is consistent with whether g halts. Therefore, the initial assumption that halts is a total computable function must be false. h(i,x) = \begin{cases} 1 & \text{if } \text{ program }i\text{ halts on input }x, \\ 0 & \text{otherwise.} \end{cases} Here program i refers to the i th program in an enumeration of all the programs of a fixed Turing-complete model of computation. 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. The proof proceeds by directly establishing that no total computable function with two arguments can be the required function h. As in the sketch of the concept, given any total computable binary function f, the following partial function g is also computable by some program e: g(i) = \begin{cases} 0 & \text{if } f(i,i) = 0,\\ \text{undefined} & \text{otherwise.} \end{cases} The verification that g is computable relies on the following constructs (or their equivalents): computable subprograms (the program that computes f is a subprogram in program e), duplication of values (program e computes the inputs i,i for f from the input i for g), 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), returning a value of 0. The following pseudocode for e illustrates a straightforward way to compute g: procedure e(i): if f(i, i) == 0 then return 0 else loop forever Because g is partial computable, there must be a program e that computes g, by the assumption that the model of computation is Turing-complete. This program is one of all the programs on which the halting function h is defined. The next step of the proof shows that h(e,e) will not have the same value as f(e,e). It follows from the definition of g that exactly one of the following two cases must hold: f(e,e) = 0 and so g(e) = 0. In this case program e halts on input e, so h(e,e) = 1. f(e,e) ≠ 0 and so g(e) is undefined. In this case program e does not halt on input e, so h(e,e) = 0. In either case, f cannot be the same function as h. Because f was an arbitrary total computable function with two arguments, all such functions must differ from h. This proof is analogous to Cantor's diagonal argument. One may visualize a two-dimensional array with one column and one row for each natural number, as indicated in the table above. The value of f(i,j) is placed at column i, row j. Because f is assumed to be a total computable function, any element of the array can be calculated using f. The construction of the function g can be visualized using the main diagonal of this array. If the array has a 0 at position (i,i), then g(i) is 0. Otherwise, g(i) is undefined. The contradiction comes from the fact that there is some column e of the array corresponding to g itself. Now assume f was the halting function h. If g(e) is defined (g(e) = 0 in this case), then the program e halts on input e, thus f(e,e) = 1. But g(e) = 0 only when f(e,e) = 0, contradicting f(e,e) = 1. Similarly, if g(e) is not defined, then program e does not halt on input e, thus f(e,e) = 0, which leads to g(e) = 0 under gs construction. This contradicts the assumption of g(e) not being defined. In both cases contradiction arises. Therefore any arbitrary computable function f cannot be the halting function h. ==Computability theory== In computability theory and computational complexity theory, a reduction is an algorithm for transforming one computational problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. There are two main types of reductions used in computational complexity theory, the many-one reduction and the Turing reduction. A set is many-one reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to many-one reducibility, the halting problem is in the most complicated class of recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem. The Turing degree groups equivalent problems into classes and the degree of the halting problem is 0′ (the "jump" of class 0) representing the class of recursively enumerable, but not recursive, sets of numbers, or similarly \Sigma^0_1 of the arithmetical hierarchy. Rice's theorem establishes that all non-trivial semantic properties of programs are undecidable and therefore in the halting problem's complexity class or a harder class. Gregory Chaitin has defined a halting probability, represented by the symbol Ω, a real number that represents the probability that a randomly produced program halts. It is a normal and transcendental number which can be defined but cannot be completely computed. The task of computing the digits of this number has the same Turing degree as the halting problem. This means one can prove that there is no algorithm which produces the digits of Ω, although its first few digits can be calculated in simple cases. Since the negative answer to the halting problem shows that there are problems that cannot be solved by a Turing machine, the Church–Turing thesis limits what can be accomplished by any machine that implements effective methods. However, not all machines conceivable to human imagination are subject to the Church–Turing thesis (e.g. oracle machines). It is an open question whether there can be actual deterministic physical processes that, in the long run, elude simulation by a Turing machine, and in particular whether any such hypothetical process could usefully be harnessed in the form of a calculating machine (a hypercomputer) that could solve the halting problem for a Turing machine amongst other things. It is also an open question whether any such unknown physical processes are involved in the working of the human brain, and whether humans can solve the halting problem. Some results have been established on the theoretical performance of halting problem heuristics, in particular the fraction of programs of a given size that may be correctly classified by a recursive algorithm. These results do not give precise numbers because the fractions are uncomputable and also highly dependent on the choice of program encoding used to determine "size". For example, consider classifying programs by their number of states and using a specific "Turing semi-infinite tape" model of computation that errors (without halting) if the program runs off the left side of the tape. Then \lim_{n\to\infty} P(x\,\text{halts is decidable} \mid x\,\text{has}\,n\,\text{states}) = 1 , over programs x chosen uniformly by number of states. But this result is in some sense "trivial" because these decidable programs are simply the ones that fall off the tape, and the heuristic is simply to predict not halting due to error. Thus a seemingly irrelevant detail, namely the treatment of programs with errors, can turn out to be the deciding factor in determining the fraction of programs. To avoid these issues, several restricted notions of the "size" of a program have been developed. A dense Gödel numbering assigns numbers to programs such that each computable function occurs a positive fraction in each sequence of indices from 1 to n, i.e. a Gödelization φ is dense iff for all i , there exists a c > 0 such that \liminf_{n\to\infty} \#\{j \in \N : 0 \leq j . For example, a numbering that assigns indices 2^n to nontrivial programs and all other indices the error state is not dense, but there exists a dense Gödel numbering of syntactically correct Brainfuck programs. A dense Gödel numbering is called optimal if, for any other Gödel numbering \alpha , there is a 1-1 total recursive function f and a constant c such that for all i , \alpha_i=\phi_{f(i)} and f(i) \leq c i . This condition ensures that all programs have indices not much larger than their indices in any other Gödel numbering. Optimal Gödel numberings are constructed by numbering the inputs of a universal Turing machine. A third notion of size uses universal machines operating on binary strings and measures the length of the string needed to describe the input program. A universal machine U is a machine for which every other machine V there exists a total computable function h such that V (x) = U (h(x)) . An optimal machine is a universal machine that achieves the Kolmogorov complexity invariance bound, i.e. for every machine V, there exists c such that for all outputs x, if a V-program of length n outputs x, then there exists a U-program of at most length n+c outputting x. We consider partial computable functions (algorithms) A . For each n we consider the fraction \epsilon_n(A) of errors among all programs of size metric at most n , counting each program x for which A fails to terminate, produces a "don't know" answer, or produces a wrong answer, i.e. x halts and A(x) outputs DOES_NOT_HALT , or x does not halt and A(x) outputs HALTS . The behavior may be described as follows, for dense Gödelizations and optimal machines: For every algorithm A , \liminf_{n\to\infty} \epsilon_n(A) > 0 . In words, any algorithm has a positive minimum error rate, even as the size of the problem becomes extremely large. There exists \epsilon > 0 such that for every algorithm A , \limsup_{n\to\infty} \epsilon_n(A) \geq \epsilon . In words, there is a positive error rate for which any algorithm will do worse than that error rate arbitrarily often, even as the size of the problem grows indefinitely. \inf_{A} \liminf_{n\to\infty} \epsilon_n(A) = 0 . In words, there is a sequence of algorithms such that the error rate gets arbitrarily close to zero for a specific sequence of increasing sizes. However, this result allows sequences of algorithms that produce wrong answers. If we consider only "honest" algorithms that may be undefined but never produce wrong answers, then depending on the metric, \inf_{A\,\textrm{honest}} \liminf_{n\to\infty} \epsilon_n(A) may or may not be 0. In particular it is 0 for left-total universal machines, but for effectively optimal machines it is greater than 0. The complex nature of these bounds is due to the oscillatory behavior of \epsilon_n(A) . There are infrequently occurring new varieties of programs that come in arbitrarily large "blocks", and a constantly growing fraction of repeats. If the blocks of new varieties are fully included, the error rate is at least \epsilon , but between blocks the fraction of correctly categorized repeats can be arbitrarily high. In particular a "tally" heuristic that simply remembers the first N inputs and recognizes their equivalents allows reaching an arbitrarily low error rate infinitely often. ==External links== Scooping the loop snooper - a poetic proof of undecidability of the halting problem animated movie - an animation explaining the proof of the undecidability of the halting problem A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium - a proof in only 13 lines haltingproblem.org - popular videos and documents explaining the Halting Problem.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378690130 under CC BY-SA 4.0; modifications have been made.