patternMinor
why is this computational method by Knuth "effective" and "powerful"?
Viewed 0 times
thiswhymethodpowerfulcomputationalknuthandeffective
Problem
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$:
He describes this formulation as effective and powerful.
My questions are:
-
What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta_j \omega$?
-
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$;
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:
-
What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta_j \omega$?
-
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$;
Solution
-
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$.
-
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}
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$.
-
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}
Context
StackExchange Computer Science Q#21564, answer score: 3
Revisions (0)
No revisions yet.