Halting problem

The halting problem describes a question in theoretical computer science.

When a plurality of processing steps be carried out according to fixed rules for the calculation produces a calculation rule, a so-called algorithm. To execute algorithms to use in theoretical computer science abstract machines. A typical abstract machine is a Turing machine.

The retaining problem describes whether the execution of an algorithm comes to an end. Although that can be easily answered for many algorithms, the mathematician Alan Turing proved that there is no algorithm that answers this question for all possible algorithms and arbitrary input. This evidence, he took on a Turing machine.

The halting problem is therefore not algorithmically decidable. The result plays a fundamental role in computability theory.

The term was not coined halting problem of Turing, but only later by Martin Davis in his book Computability and Unsolvability.

Importance

In formal systems of mathematics, there are provable statements.

Reaching formal systems a certain degree of complexity, then statements can specify which one can neither prove nor disprove. The proof of this property was in 1931 by the Austrian mathematician Kurt Gödel published ( Gödel 's incompleteness shear ). Thus Gödel pointed to the impossibility of the Hilbert program. This would establish ( unproven assumptions ) David Hilbert in 1920 the math on a complete and non-contradictory system of axioms.

Also, according to the findings of Alan Turing holds: In any formal system that contains Turing machines statements to be formulated which can neither be proved nor disproved. The halting problem describes such a statement. From the unsolvability of the halting problem follows that there are mathematical functions that, while well- defined, but not their values ​​can be calculated for each parameter. A well-known example of such a function is the Radó function.

The Church-Turing thesis states that everything that is intuitively computable by a Turing machine is computable. If this statement is true, the halting problem can not in principle be decided algorithmically. This leads to the philosophically far-reaching statement that not every problem can be solved, not even when you know all the relevant information and adheres strictly to a convincing mathematical formalism.

From the undecidability of the halting problem follows that, in general, an automated determination of logical statements ( " this state of affairs is true") - by a program logic - is not possible. In particular, it is generally not possible to automatically determine which programs ever find to an end (termination proof). For certain classes of Turing machines, however, the halting problem is decidable (for example, for programs without loops). Many occurring in practical applications and procedures are therefore structured so that on the basis of this structure, an automated termination can be carried out proof.

Illustration

For many programs, it is easy to determine if they stop at some point.

• If this program does not loop, it will always hold:

• If the running condition of a loop is always true, this program will never hold:

However, there are also programs for which it is not yet possible in the present state of knowledge to predict whether they stop for all possible input. The following program holds for each entry when the hitherto unproven Collatz Conjecture is true.

Mathematical Description

Problem

If the halting problem is decidable, there is a Turing machine that decides for each Turing machine with each input whether sometime stops or continues endlessly. The input for each consists of a coded description of the machine and its input.

Alan Turing proved in 1937 that such a machine does not exist.

Idea of ​​proof

The halting problem is decidable if and only if both the halting problem and its complement are semientscheidbar. The halting problem is obviously semientscheidbar: A universal Turing machine that receives a description of a Turing machine and a string as input holds, if and only if holds with input. It must therefore be shown that the complement of the support is not semientscheidbar problem, so that there is no Turing machine, which outputs at the input always 1, when not holding the Enter key.

This is achieved by a diagonal argument. It is first assumed that the complement of the support is semientscheidbar problem. ( The proof is thus indirectly. ) Instead of a Turing machine can also look at the function, which is calculated from it. The Turing machine computes the partial function

The size is calculated by the following function.

Be the number of a Turing machine that computes the function. The function value at the location is therefore

Sketch of proof

The proof is based on the construction of Marvin Minsky.

Step 1: The diagonal language is not semi- decidable

The set of all Turing machines that do not stop when they get their own code as input is called a diagonal language. Evidence that the diagonal language is not semientscheidbar, done by a proof by contradiction. It is believed that there is a machine which the diagonal semi- speech decision, and shows that this leads to a logical contradiction.

Suppose there is a Turing machine that outputs at input the description of a Turing machine the value if not keeping pace with input, and does not hold if halts on input from. Then would have to hold at input and output, if not halts on input, and do not hold when halts on input. This is a contradiction, such a machine can not exist then.

Step 2: The complement of the retaining problem is not semi- decidable

If the complement of the halting problem would be semi- decidable, then the diagonal language would also be semi- decidable.

Suppose there is a Turing machine that outputs at input the description of a Turing machine and a string 1, if not keeping pace with input, and does not hold if halts on input from. We may assume without loss of generality that the input for the shape. It is a character string, which occurs either in the description of the Turing machine or in its input. For a Turing machine can be constructed that the diagonal language semi- decides. starts when you enter a description of a Turing machine easy typing.

If the complement of the halting problem semi- decides to semi- decide the diagonal language. Since there can not be such a machine, the construction of out is certainly possible, it may not be such a machine.

Step 3: The halting problem is not decidable

If the halting problem would be decidable, then its complement would be semi- decidable.

Suppose there is a Turing machine that outputs at input the description of a Turing machine and a string 0 if not keeping pace with input, and outputs 1 if halts on input from. Then there would be a Turing machine that semi- decides the complement of the halting problem. starts when you enter a description of a Turing machine simply use the same input. When outputting 0, so outputs 1. If one spends so goes into an infinite loop.

If the halting problem decides as semi- decides the complement of the halting problem. Since there can not be such a machine, the construction of out is certainly possible, it may not be such a machine.

An equivalent formulation

The halting problem with empty input tape (English blank -tape halting problem-, BTHP, also known as zero - halting problem ), is the question of whether a Turing machine stops with empty input tape. The BTHP is just as hard as the halting problem. Intuitively, this is the case, because a command in the start state of a Turing machine can be encoded.

Obviously, each machine that decides the halting problem for every Turing machine with each input, opt for the BTHP. It can also be a machine that the BTHP decides for each Turing machine, already decide the general halting problem. In order to decide the halting problem for Turing machine with input, consider the Turing machine, which is defined as follows. first writes on the input tape, then behaves like. holds in particular if and only on the empty tape when holding the Enter key.