D. Knuth definition of a computational method
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 &gt;0$ as opposed to $r&gt;=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!