ABSTRACT
Let us consider a given algorithm. Because it must be computed one day, it is always possible to translate it as a Turing machine, and this last machine can be written as xn+1 = f(xn) in the following way. Let (w, i, q) be the current configuration of the Turing machine (Figure 6.1), where w = ]−ωw(0) . . . w(k)]ω is the paper tape, i is the position of the tape head, q is used for the state of the machine, and δ is its transition function (the notations used here are well-known and widely used). We define f by:
• f(w(0) . . . w(k), i, q) = (w(0) . . . w(i − 1)aw(i + 1)w(k), i + 1, q′), if δ(q, w(i)) = (q′, a,→),
• f(w(0) . . . w(k), i, q) = (w(0) . . . w(i − 1)aw(i + 1)w(k), i − 1, q′), if δ(q, w(i)) = (q′, a,←).
