Axioms defining a Turing machine

Question

I have found the following characterisation in axiomatical terms of a Turing machine:

1. $Q_0(q)\rightarrow T(q)$
2. $S_0(x)\rightarrow S(x)$
3. $C(x)\rightarrow S(x)$
4. $Q_0(q)\land T(qx)\land S(y)\rightarrow T(qxy)$
5. $R(qx,q'y)\land T(wqxz)\rightarrow T(wyq'z)$
6. $S_0(x)\land Q(q)\land T(zq)\rightarrow T(zqx)$
7. $L(qx,q'y)\land T(wuqxz)\land S(u)\rightarrow T(wq'uyz)$
8. $S_0(x)\land Q(q)\land T(qz)\rightarrow T(xqz)$
9. $T(xqy)\land F(q)\rightarrow D(xy)$
10. $S_0(x)\land D(xy)\rightarrow D(y)$
11. $S_0(y)\land D(xy)\rightarrow D(x)$
12. $D(\lambda)\rightarrow O(\lambda)$
13. $D(x)\land C(x)\rightarrow O(x)$
14. $D(xyz)\land C(x)\land C(z)\rightarrow O(xyz)$

where, I read (V. Manca, Logica matematica, 'mathematical logic'), $T(\alpha q\beta)$ expresses that there is word $\alpha\beta$ on the input tape of the machine, the machine is in state $q$, reads the first symbol of word $\beta$, which occupies the right part of the tape, while on the left of the reading cell there is word $\alpha$. $S(x)$ means that $x$ is a symbol, $S_0(x)$ means that $x$ is the blank symbol, $C(x)$ means that $x$ is a coloured symbol, $Q(q)$ means that $q$ is a state and $Q_0(q)$ means that $q$ is the initial state, $F(q)$ means that $q$ is a final state and $R(qx,q'y)$ (respectively $L(qx,q'y)$) instructs to replace $x$ by $y$, when reading it while the machine is in state $q$, to switch to state $q'$ and to move one step to the right (resp. left).

I understand that the first three implications just mean that the initial state "starts the machine", and that the initial symbol and the coloured symbols are symbols. The points from 10 to 14, if I correctly understand, define the last steps of the generation of a word: I think that property $D$ belongs to the stopped tape, which undergoes a process of cutting of the blank ends. Here my problems begin: how do we see that there may exist stopped tapes of finite length if axiom 4 says -if i correctly understand- that if $x$ is met on the tape while in the initial state, then the following tape can be any infinite sequence?

In axioms 6 and 8 must we read that for any string $z$ found on the left (or resp. right) while in state $q$ we must add the blank symbol -say $a_0$- at its right (resp. left)? Does this procedure apply only when there is an empty string on the left (resp. right)?

I have a great confusion possibly because I do not understand what predicate $T$ really means. I have searched the Internet very much, but I have found no description of this set of axioms and how they relate to the common intuitive description of a Turing machine with its tape. Could anybody explain this issue and/or give some links to resources describing how to read the above written axioms? I $\infty$-ly thank you!

Answer 1

Your questions should be answered in the book, either via explanations or via examples. Let me just add the descriptions of the two predicates $D$ and $O$. $D(x)$ means that $x$ is the contents of the tape, minus possibly leading and trailing blanks. $O(x)$ means that the machine outputs $x$. $\lambda$ is the empty string.

Under this set of axioms, $O(x)$ is true if there exists some (finite!) input $w$ for which the Turing machine outputs $x$. This non-deterministic part ("there exists some input $w$") is implemented by axiom (4), which tacitly assumes that no transitions go back to the initial state. Another possibility would have been to have a single output which corresponds to a run of the machine on the empty tape; this is tantamount to removing axiom (4).

I have never seen this list of axioms, and I daresay it's nothing standard. That's why you couldn't find it anywhere.