When does a Turing machine crash?

Turing machine

A model of an abstract computer introduced by A. Turing in 1936, which is "universal in computation".

Formally, a (deterministic 1-band-1-head) Turing machine is a tuple (∑, A, Q, δ, q0, F.), where ∑ ⊇ A. ∪ {b} the (finite) ribbon alphabet, A. the input alphabet, bA. a special symbol (space, "blank"), Q a finite set of states, q0Q the initial state, F.Q is the set of end states as well as the state transition function.

A Turing machine works on an infinite band on both sides with (countable) infinitely many adjacent fields, each labeled with a character, almost all fields with the character δ (i.e., they are "empty"). The machine works on this belt, on which exactly one field is always marked, step-by-step according to the state transition function S, i. This means that it is in exactly one of the states before and after each executed step qQ, and reads the character in the marked field a ∈ ∑. With each step it goes into a (possibly new) state q′ ∈ Q over and leads according to δ exactly one of three possible actions:

Is δ(q, a) = (q′, a′, x), it swaps the current character a on the marked field against the (possibly other) character a′ ∈ ∑. Then the marking moves one step to the right (if x = r) or to the left (if x = l), and the state goes from q to q' above. The machine stops exactly when it has reached an end state qF. device, or if δ(q, a) is not defined.

A Turing machine can be an arithmetic function in the following wayf calculate: With the help of the alphabet A. are natural numbers z. B. represented in binary or decimal. At the beginning of the calculation, the arguments of the function value to be calculated are coded in this way immediately to the right of the marking on the tape; if there are several arguments, separated by a "blank". All other fields are labeled with "blanks". In addition, the machine is in the initial state q0. Now it carries out the calculation in the above way according to the specified state transition function. If the machine stops after a finite number of steps and there is a permissible function value on the tape immediately to the right of the marking, with all other fields being empty, the calculation has been successfully completed. In all other cases the function value remains undefined (partial function).

An arithmetic function that can be calculated in this way by a Turing machine is called a (Turing) calculable function. This term is independent of the underlying formalism. In particular, it is irrelevant for the concept of calculation whether a Turing machine with one or more (or multi-dimensional) belts or separate input and output belts is used, or whether one or more (or separate) read and write heads are used.