TAOCP 1.1 Exercise 9
Let C_1=(Q_1,I_1,\Omega_1,f_1), \qquad C_2=(Q_2,I_2,\Omega_2,f_2) be computational methods in the sense of Eqs.
Exercise 9. ▶ [M30] Suppose that $C_1 = (Q_1, I_1, \Omega_1, f_1)$ and $C_2 = (Q_2, I_2, \Omega_2, f_2)$ are computational methods. For example, $C_1$ might stand for Algorithm E as in Eqs. (2), except that $m$ and $n$ are restricted in magnitude, and $C_2$ might stand for a computer program implementation of Algorithm E. (Thus $Q_2$ might be the set of all states of the machine, i.e., all possible configurations of its memory and registers; $f_2$ might be the definition of single machine actions; and $I_2$ might be the set of initial states, each including the program that determines the greatest common divisor as well as the particular values of $m$ and $n$.)
Formulate a set-theoretic definition for the concept “$C_2$ is a representation of $C_1$” or “$C_2$ simulates $C_1$.” This is to mean intuitively that any computation sequence of $C_1$ is mimicked by $C_2$, except that $C_2$ might take more steps in which to do the computation and it might retain more information in its states. (We thereby obtain a rigorous interpretation of the statement, “Program $X$ is an implementation of Algorithm $Y$.”)
Verified: yes
Solve time: 1m55s
Setup
Let
$$ C_1=(Q_1,I_1,\Omega_1,f_1), \qquad C_2=(Q_2,I_2,\Omega_2,f_2) $$
be computational methods in the sense of Eqs. (2). A computation sequence of $C_i$ is a finite sequence
$$ q_0,q_1,\ldots,q_t $$
such that $q_0\in I_i$, $q_t\in\Omega_i$, and
$$ q_{k+1}=f_i(q_k), \qquad 0\le k<t. $$
The problem asks for a set-theoretic definition expressing that $C_2$ simulates $C_1$. Intuitively, a state of $C_2$ may contain additional information, and several steps of $C_2$ may correspond to one step of $C_1$.
Solution
A simulation should identify, for every state of $C_2$, the state of $C_1$ that it represents. Therefore introduce a mapping
$$ \rho:Q_2\to Q_1, $$
called the representation map.
The statement that $C_2$ represents $C_1$ means that $\rho$ satisfies the following conditions.
First, initial states correspond:
$$ \rho(I_2)=I_1. $$
Thus every computation of $C_1$ can be started by some initial state of $C_2$, and every initial state of $C_2$ represents an initial state of $C_1$.
Second, terminal states correspond:
$$ \rho(\Omega_2)=\Omega_1. $$
Hence a computation of $C_2$ terminates exactly when the represented computation of $C_1$ has terminated.
Third, each step of $C_1$ is realized by a finite nonempty sequence of steps of $C_2$. Formally, for every $q\in Q_2$ there exists an integer $k(q)\ge1$ such that
$$ \rho!\left(f_2^{,k(q)}(q)\right) =f_1(\rho(q)), \tag{1} $$
and for
$$ 0<j<k(q) $$
we have
$$ \rho!\left(f_2^{,j}(q)\right)=\rho(q). \tag{2} $$
Equation (2) states that the intermediate states of $C_2$ do not yet advance the simulated computation. Equation (1) states that after finitely many machine steps, one step of $C_1$ has been completed.
Now consider any computation sequence of $C_1$,
$$ p_0,p_1,\ldots,p_t, $$
where
$$ p_{i+1}=f_1(p_i). $$
Choose $q_0\in I_2$ with $\rho(q_0)=p_0$. Repeated application of (1) produces integers
$$ k_0,k_1,\ldots,k_{t-1} $$
such that
$$ \rho!\left(f_2^{,k_0+\cdots+k_{i-1}}(q_0)\right)=p_i \qquad (0\le i\le t). $$
Hence the computation of $C_1$ is reproduced by a computation of $C_2$, although each transition $p_i\mapsto p_{i+1}$ may require several steps of $C_2$.
Therefore a rigorous definition is:
$C_2$ is a representation (or simulation) of $C_1$ if there exists a surjective mapping $\rho:Q_2\to Q_1$ satisfying
$$ \rho(I_2)=I_1,\qquad \rho(\Omega_2)=\Omega_1, $$
and for every $q\in Q_2$ there exists $k(q)\ge1$ such that
$$ \rho(f_2^{k(q)}(q))=f_1(\rho(q)), $$
while
$$ \rho(f_2^{j}(q))=\rho(q) \qquad (0<j<k(q)). $$
Under these conditions every computation sequence of $C_1$ is the image under $\rho$ of a computation sequence of $C_2$.
Verification
The map $\rho$ allows many states of $C_2$ to represent the same state of $C_1$, which accounts for additional registers, memory locations, or bookkeeping information.
The integer $k(q)$ may exceed $1$, which allows one step of $C_1$ to be implemented by several elementary steps of $C_2$.
The conditions on $I_2$ and $\Omega_2$ ensure that starting and terminating computations correspond under the representation map.
If $k(q)=1$ for all $q$, then
$$ \rho(f_2(q))=f_1(\rho(q)), $$
so each step of $C_2$ corresponds exactly to one step of $C_1$. The definition therefore includes exact implementations as a special case.
Notes
An equivalent formulation may be given by replacing the state-dependent integer $k(q)$ with a relation between complete computation sequences. The formulation above is closer to the intuition that a machine program realizes each abstract algorithmic step by a finite sequence of lower-level operations.