# Concatenation of URM Programs is Associative

## Theorem

Let $P, Q, R$ be one-variable URM programs.

Then the concatenated URM programs $P * \paren {Q * R}$ and $\paren {P * Q} * R$ are the same.

## Proof

For ease of analysis, let us assume that:

- Each of $P$ and $Q$ have already had the appropriate Clear Registers Program $\map Z {2, \map \rho P}$ and $\map Z {2, \map \rho Q}$ appended to them
- Each of $P$ and $Q$ have already had the appropriate amendments made to their exit jumps so as to lead to the first line of the appropriate Clear Registers Program. (Note that if the latter is a null URM program, this will be the line immediately following the end of the program).

Thus we can discuss $P$ and $Q$ without reference to these technical details.

When concatenating programs, the only amendments made to the programs themselves are to the contents of the `Jump`.

So it is clear that the number, type and order of the basic instructions of both programs are the same.

All we have to consider are the amendments to the `Jump`s.

Suppose the lengths of $P$ and $Q$ are as follows:

- $\map \lambda P = t$
- $\map \lambda Q = s$

First we look at the `Jump`s of $R$.

When we form $\paren {Q * R}$, every `Jump` of $R$ of the form $\map J {m, n, q}$ is replaced by $\map J {m, n, q + s}$.

Then when forming $P * \paren {Q * R}$ the `Jump` $\map J {m, n, q + s}$ is replaced by $\map J {m, n, q + s + t}$.

On the other hand, when we form $\paren {P * Q} * R$, every `Jump` of $R$ of the form $\map J {m, n, q}$ is replaced directly by $\map J {m, n, q + \paren {s + t} }$.

Thus the `Jump`s of $R$ have been replaced by the same instructions in each of $\paren {P * Q} * R$ and $P * \paren {Q * R}$.

Now we look at the `Jump`s of $Q$.

When forming $\paren {Q * R}$, we have already ensured that every `Jump` of $Q$ of the form $\map J {m, n, q}$ where $q > s$ has been replaced by $\map J {m, n, s + 1}$.

So when forming $P * \paren {Q * R}$ the `Jump` $\map J {m, n, s + 1}$ is replaced by $\map J {m, n, s + t + 1}$.

On the other hand, when forming $\paren {P * Q}$, every `Jump` of $Q$ of the form $\map J {m, n, q}$ is replaced by $\map J {m, n, q + t}$.

We have that $\paren {P * Q}$ has $s + t$ instructions. When $q > s$, we take account of the fact that $q + t > s + t$.

So in $\paren {P * Q} * R$, `Jump`s of the form $\map J {m, n, s + 1}$ are replaced by $\map J {m, n, s + t + 1}$.

This agrees with the corresponding `Jump`s in $P * \paren {Q * R}$.

Similarly, we can show that all other `Jump`s of $Q$, and all `Jump`s of $P$, are amended in exactly the same way in each of $\paren {P * Q} * R$ and $P * \paren {Q * R}\right)$.

Hence the result.

$\blacksquare$