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

<blockquote>
  <p>A <strong>computational method</strong> 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$ <em>pointwise fixed</em>, i.e.: $\forall q \in \Omega, f(q) = q$.</p>
</blockquote>

<p>The intended, informal meanings of these terms are the following:</p>

<blockquote>
  <p>$\fbox{Q}$ the <strong>states</strong> of the computation<br></p>
  
  <p>$\fbox{I}$ the <strong>input</strong><br></p>
  
  <p>$\fbox{$\Omega$}$ the <strong>output</strong><br></p>
  
  <p>$\fbox{f}$ the computational <strong>rule</strong></p>
</blockquote>

<p>Although irrelevant to our discussion, Knuth then defines the notion of <em>algorithm</em> as follows:</p>

<blockquote>
  <p>An <strong>algorithm</strong> is a <em>computational method</em> that terminates in finitely many steps for all $x \in I$.</p>
</blockquote>

<p>On page 8 he gives an explication of a <code>gcd</code> 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:</p>

<blockquote>
  <p><strong>Occurs</strong> $(\theta, \sigma) =_{df} \exists \alpha,\omega \in A^*(\sigma = \alpha\theta\omega)$.</p>
  
  <p><strong>Shortest</strong> $(\sigma, \Sigma, \phi) =_{df} \phi(\sigma) \land \forall\tau\in\Sigma(\phi(\tau) \rightarrow [\tau] &gt; [\sigma])$, where [&sigma;] is the <em>length</em> of &sigma;. </p>
</blockquote>

<p>With these, we're ready to make sense of f. It maps strings &sigma; and natural  numbers j to:</p>

<blockquote>
  <p>$(\sigma, \alpha_j)$ $~~~~~~~~$if$~~$ $\lnot Occurs(\theta_j,\sigma)$<br></p>
  
  <p>$(\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])$<br></p>
  
  <p>$(\sigma, N)$ $~~~~~~~~$ otherwise</p>
</blockquote>

<p>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.</p>

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

CC BY-SA 3.0
2013-10-03T08:21:32.760Z
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
CC BY-SA 3.0
2013-10-03T18:06:50.000Z
(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
CC BY-SA 3.0
2013-10-03T18:20:16.943Z
(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
CC BY-SA 3.0
2013-08-16T21:29:19.777Z
2013-08-16T23:01:56.940Z
2013-08-16T23:01:56.940Z
Hunan Rostomyan
<p>The last computational method example Knuth gives in 1.1 of Vol. 1 of 'The Art of Computer Programming' is defined by the following:</p>

<p>Let $A$ be a finite set of letters</p>

<p>Let $A^*$ be the set of all strings on A</p>

<p>Let $N$ be a nonnegative integer</p>

<p>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)</p>

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

<p>Let $\Omega$ be the subset of $Q$ with $j=N$</p>

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

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

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

<p>$f(\sigma,N)$ = $(\sigma,N)$.</p>

<hr>

<p>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.</p>

<ds.algorithms>
How does this computational method work?
sanghan
# How does this computational method work?

(Asked by: username_0 on 2013-08-15)

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.

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2013-08-16. Score: 2

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.

> **Comments:**
> **username_2**: 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?  
> **username_1**: (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]$).  
> **username_1**: (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).  

---

