Effective formal algorithm for computing GCD

Question

Hello everybody I am currently so stuck at solving this problem in the first Volume of The Art of Computer Programming:

[M25] Give an "effective" formal algorithm for computing the greatest common divisor of positive integers $m$ and $n$, by specifying $\theta_j$, $\phi_j$, $a_j$, $b_j$ as in Eqs. (3). Let the input be represented by the string $a^mb^n$, that is, $m$ $a$'s followed by $n$ $b$'s. Try to make your solution as simple as possible. [$Hint$: Use Algorithm E, but instead of division in step E1, set $r \leftarrow |m-n|$, $n \leftarrow min(m,n)$.]

Now this is the part related to Eqs. (3):
Let $A$ be a finite set of letters, and let $A^*$ be the set of all strings on $A$ (the set of all ordered sequences $x_1x_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 nonnegative integer and let $Q$ be the set of all $(\sigma,j)$, where $\sigma$ is in $A^*$ and $j$ is an integer, $0 \le j \le N$; let $I$ be the subset of $Q$ with $j=0$ and let $\Omega$ 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 < 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)$.
$(3)$

And finally this is the Algorithm E:
Algorithm E $(Euclid's \, algorithm)$. Given two positive integers $m$ and $n$, find their $greatest \, common \, divisor$, that is, the largest positive integer that evenly divides both $m$ and $n$.
E1. [Find remainder] Divide $m$ by $n$ and let $r$ be the remainder. (We will have $0 \le r < n$.)
E2. [Is it zero?] If $r=0$, the algorithm terminates; $n$ is the answer.
E3. [Reduce] Set $m \leftarrow n, \, n \leftarrow r$, and go back to step E1.

I am really happy and I appreciate anyone who comes by and help me because I've spent hours without success in finding the suitable parameters. Thank you StackExchange.

Answer 1

Eqs. (3) seems to define a machine that do the followings:

1. Operation steps are numbered by $j$.
2. In step $j$, the machine detects the first occurrence of $\theta_j$ in $\sigma$, and replaces $\sigma = \alpha\theta_j\omega$ by new $\sigma=\alpha\phi_j\omega$. Then go to step $b_j$.
3. If $\theta_j$ does not presence, then go to step $a_j$.

---

My solution

Assume the input is $(\underbrace{a...a}_m\underbrace{b...b}_n, 1)$ and let $\epsilon\in A^*$ denote the empty string. My plan is as the following:

Step 1.

Detect ab in $\sigma$ and replace ab by ab (ie, no replacement). Then go to step 2.

If ab does not presence in $\sigma$, then go to step 4.

Step 2.

Replace the first occurance of a by ca. That is, append a c before the first a.

It is impossible that there is no a in $\sigma$, because we are from step 1. So we go to step 3 directly.

Step 3.

Delete ab in $\sigma$, and then go to step 1.

Again, it is impossible that there is no ab in $\sigma$.

---

So far, the modified first step of Algorithm E is implemented. The steps are encoded in the table:

$$\begin{array}{|c|c|c|c|c|} \hline j & \theta_j & \phi_j & a_j & b_j \\ \hline 1 & ab & ab & 4 & 2 \\ \hline 2 & a & ca & \text{any} & 3 \\ \hline 3 & ab & \epsilon & \text{any} & 1 \\ \hline 4 & ... & ... & ... & ... \\ \hline \end{array}.$$

For example:

$(aaaaa\,bb, 1)\to (aaaaa\,bb, 2)\to (c\,aaaaa\,bb, 3)\\ \to (c\,aaaa\,b, 1)\to (c\,aaaa\,b, 2)\to (cc\,aaaa\,b, 3)\\ \to (cc\,aaa, 1)\to (cc\,aaa, 4)\to ...$

Observe that $a^5b^2$ becomes $c^2a^{5-2}$. These steps can also transform $a^2b^5$ into $c^2b^{5-2}$

In steps 4-? we transform $c^mb^n$ or $c^na^m$ to the original form $a^mb^n$ so that we can apply steps 1-3 again and again.

---

Step 4.

Detect cb. If cb exists in $\sigma$ then we know that $\sigma$ is of the form $c^mb^n$. Go to step 5.

If there is no cb, then go to step 6.

Step 5.

We have to replace c by a repeatedly. So we detect c and replace it by a, and then go to step 5 again.

If there is no c remaining, then we can go to step 1.

Step 6.

Detect ca. If ca exists in $\sigma$ then we know that $\sigma$ is of the form $c^na^m$. Go to step 7.

If there is also no ca, then there are only c in $\sigma$. Go to step 10 and terminate the process.

Step 7.

We have to detect c and then append b in the end of $\sigma$. If c is detected, go to the next step to append b.

If there is no c remaining, then we can go to step 1.

Step 8.

Replace a by ab, ie, append a b after a. Then go to step 9.

Step 9.

Remove the leading c and go bacj to step 7 to check for remaining c again.

Step 10.

There are only some c in $\sigma$. The length of cs is the g.c.d. Note that $N=10$ in this algorithm.

$$\begin{array}{|c|c|c|c|c|} \hline j & \theta_j & \phi_j & a_j & b_j \\ \hline 4 & cb & cb & 6 & 5 \\ \hline 5 & c & a & 1 & 5 \\ \hline 6 & ca & ca & 10 & 7 \\ \hline 7 & c & c & 1 & 8 \\ \hline 8 & a & ab & \text{any} & 9 \\ \hline 9 & c & \epsilon & \text{any} & 7 \\ \hline 10& - & - & - & - \\ \hline \end{array}.$$