How does this computational method work?

Question

The last computational method example Knuth gives in 1.1 of Vol. 1 of 'The Art of Computer Programming' is defined by the following:

Let $A$ be a finite set of letters

Let $A^*$ be the set of all strings on A

Let $N$ be a nonnegative integer

Let $Q$ be the set of all $(\sigma,j)$ where $\sigma$ is in $A^*$ and $j$ is an integer $0\leq j\leq N$. ($Q$ denotes the states of computation in a computational method)

Let $I$ be the subset of $Q$ with $j=0$. ($I$ denotes the inputs in a computational method)

Let $\Omega$ be the subset of $Q$ with $j=N$

Let $f$ be a function, defined by the strings $\theta_j, \phi_j$ and the integers $a_j, b_j$ for $0\leq j < N$

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

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

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

---

What I don't understand is how the function works other than the last part where every output points to itself. Can someone please shed some light on what the first two function definitions are doing.

Answer 1

Before we look at what f does, let's look at some of Knuth's definitions earlier in the chapter.

A computational method is a quadruple ($Q, I, \Omega, f$) where $I,\Omega \subseteq Q$ and $f : Q \mapsto Q$; and $f$ has the property of leaving $\Omega$ pointwise fixed, i.e.: $\forall q \in \Omega, f(q) = q$.

The intended, informal meanings of these terms are the following:

$\fbox{Q}$ the states of the computation

$\fbox{I}$ the input

$\fbox{$\Omega$}$ the output

$\fbox{f}$ the computational rule

Although irrelevant to our discussion, Knuth then defines the notion of algorithm as follows:

An algorithm is a computational method that terminates in finitely many steps for all $x \in I$.

On page 8 he gives an explication of a gcd algorithm in terms of this formal notion. Now, getting back to f, it would be helpful if we keep the following auxiliary definitions in sight:

Occurs $(\theta, \sigma) =_{df} \exists \alpha,\omega \in A^*(\sigma = \alpha\theta\omega)$.

Shortest $(\sigma, \Sigma, \phi) =_{df} \phi(\sigma) \land \forall\tau\in\Sigma(\phi(\tau) \rightarrow [\tau] > [\sigma])$, where [σ] is the length of σ.

With these, we're ready to make sense of f. It maps strings σ and natural numbers j to:

$(\sigma, \alpha_j)$ $~~~~~~~~$if$~~$ $\lnot Occurs(\theta_j,\sigma)$

$(\alpha\phi_j\omega, b_j)$ $~~$if$~~$ $\exists\alpha\in A^*(\sigma = \alpha\theta_j\omega \land Shortest(\alpha, A^*, [\lambda x.\sigma = x\theta_j\omega])$

$(\sigma, N)$ $~~~~~~~~$ otherwise

Informally, we can describe f's behavior as follows. If no two strings $\alpha$ and $\omega$ exist in $A^*$ that can be wrapped around $\theta_j$ to make $\sigma$, then f returns $\sigma$ with its index $a_j$ (i'm not sure why Knuth differentiates between $a_j$ and $j$ s.t. $0 \leq j \leq N$). Else, if there exist strings $\alpha$ and $\omega$ that can be wrapped around $\theta_j$ in the following way: $\alpha\theta_j\omega$, to make $\sigma$, then f returns: the sequence of the shortest $\alpha$ that makes that equality true, $\phi_j$, $\omega$, along with the index $b_j$. In all the other cases, f returns $\sigma$ with the index N.

Hope this helps. If you find errors, feel free to edit this post or add a comment below.