halting problem - GudangMovies21

Source: Halting problem

In 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. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting 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 f that might determine whether programs halt, that a "pathological" program g exists for which f makes an incorrect determination. Specifically, g is the program that, when called with some input, passes its own source and its input to f and does the opposite of what f predicts g will do. The behavior of f on g shows undecidability as it means no program f will solve the halting problem in every possible case.

Background

halting

problem

halting

problem

= Programming consequences

= Common pitfalls

History

problem

halting

problem

= Timeline

= Origin of the halting problem

Formalization

= Representation as a set

= Proof concept

halting

problem

= Sketch of rigorous proof

halting

Computability theory

= Approximations

. For example, a numbering that assigns indices

2

n

{\displaystyle 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

α

{\displaystyle \alpha }

, there is a 1-1 total recursive function

f

{\displaystyle f}

and a constant

c

{\displaystyle c}

such that for all

i

{\displaystyle i}

,

α

i

=

ϕ

f
(
i
)

{\displaystyle \alpha _{i}=\phi _{f(i)}}

and

f
(
i
)
≤
c
i

{\displaystyle f(i)\leq ci}

. 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
)
)

{\displaystyle 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

{\displaystyle n+c}

outputting x.
We consider partial computable functions (algorithms)

A

{\displaystyle A}

. For each

n

{\displaystyle n}

we consider the fraction

ϵ

n

(
A
)

{\displaystyle \epsilon _{n}(A)}

of errors among all programs of size metric at most

n

{\displaystyle n}

, counting each program

x

{\displaystyle x}

for which

A

{\displaystyle A}

fails to terminate, produces a "don't know" answer, or produces a wrong answer, i.e.

x

{\displaystyle x}

halts and

A
(
x
)

{\displaystyle A(x)}

outputs DOES_NOT_HALT, or

x

{\displaystyle x}

does not halt and

A
(
x
)

{\displaystyle A(x)}

outputs HALTS. The behavior may be described as follows, for dense Gödelizations and optimal machines:

For every algorithm

A

{\displaystyle A}

,

lim inf

n
→
∞

ϵ

n

(
A
)
>
0

{\displaystyle \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

ϵ
>
0

{\displaystyle \epsilon >0}

such that for every algorithm

A

{\displaystyle A}

,

lim sup

n
→
∞

ϵ

n

(
A
)
≥
ϵ

{\displaystyle \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

lim inf

n
→
∞

ϵ

n

(
A
)
=
0

{\displaystyle \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

honest

lim inf

n
→
∞

ϵ

n

(
A
)

{\displaystyle \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

ϵ

n

(
A
)

{\displaystyle \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

ϵ

{\displaystyle \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.

= Gödel's incompleteness theorems

=

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 an axiomatization of the natural numbers that is both complete and sound is impossible. The "sound" part is the weakening: it means that we require the axiomatic system in question to prove only true statements about natural numbers. Since soundness implies consistency, this weaker form can be seen as a corollary of the strong form. It is important to observe that the statement of the standard form of Gödel's First Incompleteness Theorem is completely unconcerned with the truth value of a statement, but only concerns the issue of whether it is possible to find it through a mathematical proof.
The weaker form of the theorem can be proved from the undecidability of the halting problem as follows. Assume that we have a sound (and hence consistent) and complete axiomatization of all true first-order logic statements about natural numbers. Then we can build an algorithm that enumerates all these statements. This means that there is an algorithm N(n) that, given a natural number n, computes a true first-order logic statement about natural numbers, and that for all true statements, there is at least one n such that N(n) yields that statement. Now suppose we want to decide if the algorithm with representation a halts on input i. We know that this statement can be expressed with a first-order logic statement, say H(a, i). Since the axiomatization is complete it follows that either there is an n such that N(n) = H(a, i) or there is an n′ such that N(n′) = ¬ H(a, i). So if we iterate over all n until we either find H(a, i) or its negation, we will always halt, and furthermore, the answer it gives us will be true (by soundness). This means that this gives us an algorithm to decide the halting problem. Since we know that there cannot be such an algorithm, it follows that the assumption that there is a consistent and complete axiomatization of all true first-order logic statements about natural numbers must be false.

Generalization

Many variants of the halting problem can be found in computability textbooks. Typically, these problems are RE-complete and describe sets of complexity

Σ

1

0

{\displaystyle \Sigma _{1}^{0}}

in the arithmetical hierarchy, the same as the standard halting problem. The variants are thus undecidable, and the standard halting problem reduces to each variant and vice-versa. However, some variants have a higher degree of unsolvability and cannot be reduced to the standard halting problem. The next two examples are common.

= Halting on all inputs

=
The universal halting problem, also known (in recursion theory) as totality, is the problem of determining whether a given computer program will halt for every input (the name totality comes from the equivalent question of whether the computed function is total).
This problem is not only undecidable, as the halting problem is, but highly undecidable. In terms of the arithmetical hierarchy, it is

Π

2

0

{\displaystyle \Pi _{2}^{0}}

-complete.
This means, in particular, that it cannot be decided even with an oracle for the halting problem.

= Recognizing partial solutions

=
There are many programs that, for some inputs, return a correct answer to the halting problem, while for other inputs they do not return an answer at all.
However the problem "given program p, is it a partial halting solver" (in the sense described) is at least as hard as the halting problem.
To see this, assume that there is an algorithm PHSR ("partial halting solver recognizer") to do that. Then it can be used to solve the halting problem,
as follows:
To test whether input program x halts on y, construct a program p that on input (x,y) reports true and diverges on all other inputs.
Then test p with PHSR.
The above argument is a reduction of the halting problem to PHS recognition, and in the same manner,
harder problems such as halting on all inputs can also be reduced, implying that PHS recognition is not only undecidable, but higher in the arithmetical hierarchy, specifically

Π

2

0

{\displaystyle \Pi _{2}^{0}}

-complete.

= Lossy computation

=
A lossy Turing machine is a Turing machine in which part of the tape may non-deterministically disappear. The halting problem is decidable for a lossy Turing machine but non-primitive recursive.

= Oracle machines

=

A machine with an oracle for the halting problem can determine whether particular Turing machines will halt on particular inputs, but they cannot determine, in general, whether machines equivalent to themselves will halt.

Notes

References

Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
Copeland, B. Jack, ed. (2004). The essential Turing : seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma. Oxford: Clarendon Press. ISBN 0-19-825079-7.
Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill..
Rogers, Hartley (Jr.) (1957). Theory of Recursive Functions and Effective Computability. Massachusetts Institute of Technology.
Kleene, Stephen Cole (1952). Introduction to metamathematics. North-Holland. ISBN 0923891579.. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.
Lucas, Salvador (June 2021). "The origins of the halting problem". Journal of Logical and Algebraic Methods in Programming. 121: 100687. doi:10.1016/j.jlamp.2021.100687. hdl:10251/189460. S2CID 235396831.
Minsky, Marvin (1967). Computation: finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall. ISBN 0131655639.. See chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
Moore, Cristopher; Mertens, Stephan (2011). The Nature of Computation. Oxford University Press. doi:10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2.
Reid, Constance (1996). Hilbert. New York: Copernicus. ISBN 0387946748.. First published in 1970, a fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
Sipser, Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (Second ed.). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X.
Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. s2-42 (1). Wiley: 230–265. doi:10.1112/plms/s2-42.1.230. ISSN 0024-6115. S2CID 73712., Turing, A. M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction". Proceedings of the London Mathematical Society. s2-43 (1). Wiley: 544–546. doi:10.1112/plms/s2-43.6.544. ISSN 0024-6115. This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
Penrose, Roger (1989). The emperor's new mind: concerning computers, minds, and the laws of physics (1990 corrected reprint ed.). Oxford: Oxford University Press. ISBN 0192861980.. Cf. Chapter 2, "Algorithms and Turing Machines". An over-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 81-7808-347-7.. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
Hodges, Andrew (1983). Alan Turing: the enigma. New York: Simon and Schuster. ISBN 0-671-49207-1.. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
Börger, Egon (1989). Computability, complexity, logic. Amsterdam: North-Holland. ISBN 008088704X.
Abdulla, Parosh Aziz; Jonsson, Bengt (1996). "Verifying Programs with Unreliable Channels". Information and Computation. 127 (2): 91–101. doi:10.1006/inco.1996.0053.
Collected works of A.M. Turing
Good, Irving John, ed. (1992). Pure Mathematics. North-Holland. ISBN 978-0-444-88059-8.
Gandy, R. O.; Yates, C. E. M., eds. (5 December 2001). Mathematical Logic. Elsevier. ISBN 978-0-08-053592-0.
Ince, D.C., ed. (1992). Mechanical Intelligence. North-Holland. ISBN 978-0-444-88058-1.
Saunders, P. T., ed. (26 November 1992). Morphogenesis. Elsevier. ISBN 978-0-08-093405-1.

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.

Background

= Programming consequences

= Common pitfalls

History

= Timeline

= Origin of the halting problem

Formalization

= Representation as a set

= Proof concept

= Sketch of rigorous proof

Computability theory

= Approximations

= Gödel's incompleteness theorems

Generalization

= Halting on all inputs

= Recognizing partial solutions

= Lossy computation

= Oracle machines

See also

Notes

References

Further reading

External links

Kata Kunci Pencarian:

Background

= Programming consequences

= Common pitfalls

History

= Timeline

= Origin of the halting problem

Formalization

= Representation as a set

= Proof concept

= Sketch of rigorous proof

Computability theory

= Approximations

= Gödel's incompleteness theorems

Generalization

= Halting on all inputs

= Recognizing partial solutions

= Lossy computation

= Oracle machines

See also

Notes

References

Further reading

External links

Kata Kunci Pencarian:

TAG FAVORIT

GENRE