# How does this computational method work?

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.

## 1 Answer

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.

• Can you explain what \tau is? I'm having trouble understanding that line. Also, how do I interpret that part with a lambda in it? – Nate Glenn Oct 3 '13 at 8:21
• (1/2) $\tau$, $\sigma$ are strings; $\Sigma$ is a set of strings (in the definition of f it gets called with $A^*$). The definition of Shortest says: given a string $\sigma$, a set of strings $\Sigma$, and a certain property $\phi$, we say that $\sigma$ is the shortest string in $\Sigma$ that satisfies the property $\phi$ iff (i) $\phi(\sigma)$, and (ii) every string $\tau \in \Sigma$ that also satisfies $\phi$ has a length ($[\tau]$) greater than the length of $\sigma$ ($[\sigma]$). – Hunan Rostomyan Oct 3 '13 at 18:06
• (2/2) Then in the definition of f, Shortest gets called with $\alpha$, $A^*$, and $[\lambda x. \sigma = x \theta_j \omega]$. The last argument is an implicit way of defining the property/predicate "$x\theta_j \omega$ holds for x". I assumed most were familiar with the lambda notation, so I used it to define the property. Another way would be to define the property explicitly somewhere before the definition of f by saying: P(x) is true iff $\sigma = x\theta_j \omega$. Then in the definition of f, we could just say: Shortest($\alpha$, $A^*$, P). – Hunan Rostomyan Oct 3 '13 at 18:20