3
$\begingroup$

I am new to the site and I hope after reading the guide lines i am in line with them. I am reading The Art of Computer Programming by Donald E. Knuth. The question is addressed to those having a copy of Volume 1. At pages 27-28, Knuth formally defines a computational method to be a quadruple (Q, I, $\omega$, f). I am interested in the first computational method.

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

3/ How are the values of f deduced from the algorithm?

P.S. In case my question is vague please mention in comments where i need to make things clear. And I am more after understanding the theory than any algorithm usefulness, hope that will be useful.

$\endgroup$
  • 7
    $\begingroup$ I don't think the question is vague, but I also think it is not as research-levelly as we typically expect. So maybe this is a great question for math.SE? $\endgroup$ – Raphael Nov 16 '11 at 12:33
  • 1
    $\begingroup$ @Raphael: I thought about math.SE but I realize rare are mathematicians with a copy of TAOCP. I'm still trying to understand it clearly and when I do, I'll post the answer. Thanks $\endgroup$ – Toussaint Nov 17 '11 at 22:54
  • $\begingroup$ The thing is, a couple of computer scientists roam math.SE, too, and will definitely answer the question if asked there (if they can, that is). $\endgroup$ – Raphael Nov 18 '11 at 10:51
  • 6
    $\begingroup$ There's also cs.SE! $\endgroup$ – Joshua Grochow Feb 11 '14 at 17:44
6
$\begingroup$

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

Q consists of the input $I$, output $\Omega$, and all the intermediate "states" or values during the computation. (it will be clear in the Euclid example.)

2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

Yes, those are the states of computation. Note that the input $I$ consists of all pairs of $(m,n)$, which can be seen as the initial state, and $\Omega$ consists of all singleton $(n)$, which is the output and final computation state. The quadruples ends with 1,2,3 define various states of the computation and how $f$ maps each of those states corresponds to the various steps of the Euclid's algorithm as he described earlier in the book.

Now let's run through the steps.

$f((m,n)) = (m,n,0,1);$

this just says that given an initial input of (m,n), the algorithm will transform into "state #1" of the computation. How $f$ handles state #1 is defined below. Note that the value 0 here is simply a placeholder, because the 3rd value in the quadruple is ignored in "state #1".

$f((n)) = (n);$

given a singleton (only obtained as the final result), it is mapped to itself, which indicates the termination of the computation.

$f((m,n,r,1)) = (m, n, m\bmod n, 2);$

this is the first step of the Euclid's algorithm. Given $(m, n)$ (note, value $r$ is ignored here.), compute the remainder of $m$ divided by $n$ and this new state will be mapped as follows:

$f((m,n,r,2)) = (n)$ if $r = 0$, $(m,n,r,3)$ otherwise;

note the $r$ is the remainder computed in the 1st step. If $r=0$, then this state is mapped to the singleton $(n)$, which indicates the termination of the algorithm because $(n) \in \Omega$, which means $f((n)) = (n)$. Else, it's mapped to another state and how $f$ handles this state is defined below:

$f((m,n,p,3)) = (n,p,p,1)$

Here $p$ gets the value of $r$ from the previous step. $p$ is introduced because $p >0$ as opposed to $r>=0$. This is the final step in Euclid where $m\gets n, n\gets r$, and a new state is produced with those values and f will handle this state according to "state rule #1" as defined earlier (basically computation returns to step 1).

3/ How are the values of f deduced from the algorithm?

I guess you mean the final output, which is $(n)$.

hopefully this helps!

$\endgroup$
  • $\begingroup$ I wonder why this hasn't been chosen as the answer. $\endgroup$ – Motun Jan 6 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.