Please explain this formal definition of computation

I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts::


Let $A$ be a finite set of letters. Let $A^$ be the set of all strings in $A$ (the set of all ordered sequences $x_1$ $x_2$ ... $x_n$ where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j \le N$:

• $f((\sigma, j)) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$

• $f((\sigma, j)) = (\alpha \psi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$

• $f((\sigma,N)) = (\sigma, N)$

Not being a computer scientist, I have trouble grasping the whole passage. I kind of get the idea that is behind a system of opcodes, but I haven't progressed effectively in understanding. I think that the main problem is tat I don't know how to read it effectively.

Would it be possible to explain the passage above so that I can understand it, and give me a strategy in order to get in the logic in interpreting these statements?

We are missing some context so I have no idea what point Knuth is trying to make, but here's how to interpret a Turing machine this way. Perhaps it will help you understand what's going on. In general, a good way of getting a grip on a concept is playing with it. In the case of programming paradigms, that means writing a program. In this case, I will show how to write any program.

Suppose the tape of the Turing machine has symbols $\{0,1,\epsilon\}$ (where $\epsilon$ stands for "empty"), and add one more symbol which represents the location of the head $H$. Your states are going to be pairs of the form $(q,\alpha)$, where $q$ is a state of the Turing machine, and $\alpha \in \{0,\ldots,14\}$. We also identify $(F,0)$ with $N$ for any final state.

On (non-empty) input $x$, your starting point will be $(Hx,(s,0))$, where $s$ is the starting state. The difficult part is to encode states. Suppose that at state $q$, upon reading input $x$, you replace it with $a(q,x)$, move in direction $D(q,x) \in \{L,R\}$, and switch to state $\sigma(q,x)$. For the $\theta$s, we have
$$
\begin{align*}
\theta_{q,0} &= 0H0, & \theta_{q,1} &= 0H1, & \theta_{q,2} &= 0H\epsilon, \\
\theta_{q,3} &= 1H0, & \theta_{q,4} &= 1H1, & \theta_{q,5} &= 1H\epsilon, \\
\theta_{q,6} &= \epsilon H0 & \theta_{q,7} &= \epsilon H1, & \theta_{q,8} &= \epsilon H\epsilon, \\
\theta_{q,9} &= H0, & \theta_{q,10} &= H1, & \theta_{q,11} &= H\epsilon, \\
\theta_{q,12} &= 0H, & \theta_{q,13} &= 1H, & \theta_{q,14} &= \epsilon H.
\end{align*}
$$
For the $a$s, we have $a_{q,i} = (q,i+1)$ for $i < 14$, and $a_{q,14} = (q,14)$, though we should never really get that far. For the $b$s, we have
$$
\begin{align*}
&b_{q,0} = b_{q,3} = b_{q,6} = b_{q,9} = (\sigma(q,0),0), \\
&b_{q,1} = b_{q,4} = b_{q,7} = b_{q,10} = (\sigma(q,1),0), \\
&b_{q,2} = b_{q,5} = b_{q,8} = b_{q,11} = b_{q,12} = b_{q,13} = b_{q,14} = (\sigma(q,\epsilon),0).
\end{align*}
$$
Now it remains to determine the $\psi$s. Let $a_0 = a(q,0)$. If $D(q,0) = L$ then
$$
\begin{align*}
\psi_{q,0} &= H0a_0, & \psi_{q,3} &= H1a_0, & \psi_{q,6} &= \psi_{q,9} = H\epsilon a_0.
\end{align*}
$$
If $D(q,0) = R$ then
$$
\begin{align*}
\psi_{q,0} &= 0a_0H, & \psi_{q,3} &= 1a_0H, & \psi_{q,6} &= \epsilon a_0 H, & \psi_{q,9} &= a_0H\epsilon.
\end{align*}
$$
Next, let $a_1 = a(q,1)$. If $D(q,1) = L$ then
$$
\begin{align*}
\psi_{q,1} &= H0a_1, & \psi_{q,4} &= H1a_1, & \psi_{q,7} &= \psi_{q,10} = H\epsilon a_1.
\end{align*}
$$
If $D(q,1) = R$ then
$$
\begin{align*}
\psi_{q,1} &= 0a_1H, & \psi_{q,4} &= 1a_1H, & \psi_{q,7} &= \epsilon a_1 H, & \psi_{q,10} &= a_1 H\epsilon.
\end{align*}
$$
Finally, let $a_\epsilon = a(q,\epsilon)$. If $D(q,\epsilon) = L$ then
$$
\begin{align*}
\psi_{q,2} &= H0a_\epsilon, & \psi_{q,5} &= H1a_\epsilon, & \psi_{q,8} &= \psi_{q,11} = H\epsilon a_\epsilon, \\
\psi_{q,12} &= H0a_\epsilon, & \psi_{q,13} &= H1a_\epsilon, &\psi_{q,14} &= H\epsilon a_\epsilon.
\end{align*}
$$
If $D(q,\epsilon) = R$ then
$$
\begin{align*}
\psi_{q,2} &= 0a_\epsilon H, & \psi_{q,5} &= 1a_\epsilon H, & \psi_{q,8} &= \epsilon a_\epsilon H, & \psi_{q,11} &= a_\epsilon H\epsilon, \\
\psi_{q,12} &= 0a_\epsilon H, & \psi_{q,13} &= 1a_\epsilon H, & \psi_{q,14} &= \epsilon a_\epsilon H.
\end{align*}
$$

Now apply $f$ repeatedly until you get stuck. If you follow the construction, you will see that we have simulated the running of the Turing machine.

StackExchange Computer Science Q#1666, answer score: 8