why is this computational method by Knuth "effective" and "powerful"?

Question

This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To make my question self-contained, here it goes.

Knuth introduces the following formulation which "restrict the notion of algorithm so that only elementary operations are involved", (copied from the above mentioned question):

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 \phi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$
• $f((\sigma,N)) = (\sigma, N)$

He describes this formulation as effective and powerful.

My questions are:

1. What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta_j \omega$?

2. Why is it so powerful? For example, if we are doing repeated multiplication (say compute $x^{10}$ given some $x \in I$), the string replacement values $\phi_j$ have to be predefined without knowing the value of $x$; but it seems that $\phi_j$ would have to depend on the specific value of $x$. So how does it really work?

Clearly I am missing something. Any help would be appreciated!

Answer 1

You have packed several questions into your post, but it sounds like your main question is: how do we know that this is "powerful enough to do anything we can do by hand"?

The answer is: strictly speaking, we don't. But because this is enough to express anything that can be computed on a Turing machine, we strongly expect this will be enough to express any feasible computation. See the Church-Turing thesis for a detailed explanation of this belief/hypothesis/conjecture and why it appears to be reasonable.

Answer 2

1. It's necessary to have some restriction such as "$\alpha$ is shortest possible string for which $\sigma = \alpha \theta_j \omega$" so the algorithm is unambiguous, because it's possible for $\theta_j$ to appear at multiple locations in $\sigma$.

2. After seeing Knuth's answer to exercise 1.1.8, I see how something like $x^k$ can be computed this way. Below is my rather cumbersome approach.

Let $A = \{a,b,c,d,e,t\}$ and $N=10$.

Given $x,k$ where $x>0$ and $k \ge 0$, the input will be $a^xb^k$ ($2^3$ would have input $aabbb$), and output will be the string $c^{x^k}$ ($x^k$ number of $c$'s. empty string denotes 1).

\begin{array}{cccccc} j & \theta_j & \phi_j & b_j & a_j & \text{comments}\\ 0 & b & (\text{empty}) & 1 & 9 & \text{remove one $b$. if no $b$, done.} \\ 1 & c & c & 3 & 2 & \text{if first time (no $c$'s), add $c$. else expand} \\ 2 & a & tc & 2 & 8 & \text{add a $c$ for each $a$} \\ 3 & a & t & 4 & 6 & \text{for each $a$, add in $c$ amount of $d$'s} \\ 4 & c & ed & 4 & 5 & \text{for each c, add in a $d$} \\ 5 & e & c & 5 & 3 & \text{change $e$ back to $c$} \\ 6 & c & (\text{empty}) & 6 & 7 & \text{clean up. remove all $c$'s} \\ 7 & d & c & 7 & 8 & \text{clean up. change all $d$'s back to $c$'s}\\ 8 & t & a & 8 & 0 & \text{clean up. change $t$'s to $a$'s}\\ 9 & a & (\text{empty}) & 9 & 10 & \text{remove all $a$'s. return} \end{array}

Answer 3

am skimming your questions & their answers on this subj but basically Knuth seems to be creating a rather involved representation of what Hopcroft & Ullman & others have called/defined less complexly an "instantaneous description" of the machine state.

the basic idea is that the entire current execution state of the machine including the head position can be encoded as a string, where the string contains the machine table state as a symbol embedded along with the tape symbols, and the sequence of TM operations over time can be represented as what is also called a "computational tableau" or a sequence of these strings, transformed by a single TM operation. his basic point is that operations which construct a computational tableau (via string transformations) are Turing complete. not sure of his details but that would be his justification for calling it "effective and powerful".

this is a picture from wikipedia showing a "computational tableau". the underline under a symbol indicates the head position, and note a new set of "composite" symbols "input/output symbol plus underline" can be added to represent it. the ID is the 2nd & 3rd columns encoded as a single string:

test http://upload.wikimedia.org/wikipedia/en/f/f9/State_diagram_3_state_busy_beaver_4_.JPG