重なりのある更新

メモリを、番地から値への写像 $\mu$ とみる（1 要素を 1 つの番地で代表させる）。有限集合 $J$ の各 $j$ に、出力の番地 $\omega(j)$、入力の番地 $\rho_1(j),\ldots,\rho_m(j)$ が定まっていて、$\omega$ は単射とする。関数 $f$ による更新の 2 通りの実行を考える。

• 一時配列を使う実行: すべての $j$ について $\tau_j=f(\mu(\rho_1(j)),\ldots,\mu(\rho_m(j)))$ を先に計算し、そのあとで $\mu(\omega(j))$ を $\tau_j$ に書き換える。
• 逐次実行: $J$ の元をある順序 $j_1,j_2,\ldots$ に並べ、順に「その時点のメモリから $\rho_1(j_t),\ldots,\rho_m(j_t)$ を読み、$f$ の値を $\omega(j_t)$ に書く」を行う。

このとき次が成り立つ。

1. $j\ne j'$ ならばすべての $l$ で $\omega(j)\ne\rho_l(j')$ である（ある要素の出力先を、別の要素の計算が読まない）とき、逐次実行の結果は順序によらず、一時配列を使う実行の結果と一致する。とくに、出力の番地の集合と入力の番地の集合が交わらないとき、および出力と入力がまったく同じ配置（$\omega(j)=\rho_1(j)$ で、ほかに重なりがない）のときにそうである。
2. 長さ $n\ge3$ の配列 $a$ に対する a[1:] += a[:-1]（$J=\{1,\ldots,n-1\}$, $\omega(j)=\rho_1(j)=j$, $\rho_2(j)=j-1$, $f(x,y)=x+y$）は 1 の条件を満たさない。一時配列を使う実行の結果は $a'_j=a_j+a_{j-1}$、添字の小さい順の逐次実行の結果は $a'_j=a_0+a_1+\cdots+a_j$（累積和）で、$a_0\ne0$ ならば $j=2$ で異なる。