Equivalence of two WordRAM models up to polylogarithmic overhead

WordRAM.APSPBridge.uniform_simulation_exists. There exists one natural exponent $d$ for which all five assertions below hold. Here the natural-addressed machine has memory on $\mathbb N$, positive bit width $s$, and a fixed finite width-independent program with copy, modular addition/subtraction/multiplication, zero-filling shifts by unsigned word amounts, bitwise AND/OR/NOT, jumps, unsigned equality/order branches, and explicit halt; direct addresses are arbitrary naturals, indirect pointers are unsigned words, natural immediate constants are reduced modulo $2^s$, and there are no native constants. Its runs start at program counter and tick count zero with halt flag false; every instruction including halt costs one step, and invalid fetches are stuck without halting. The signed-addressed machine has memory on $\mathbb Z$ and finite programs with constant-one writes, modular addition/subtraction/multiplication, signed-pointer loads/stores, branches on a negative signed word, accept and reject; all instructions cost one step, including the default rejection at an out-of-range program position. Halting within a natural fuel bound means that the specified verdict and whole final memory have been returned by that bound, not necessarily for the first time exactly then; zero fuel never gives a successful halt. (i) For every natural-addressed program $P$ there exist a signed-addressed program $Q$ and positive natural $C$, fixed before the width and input, such that for every positive source width $s$ and every arbitrary source memory $m$, initialize $Q$ at width $s+4$ with cell $0$ equal to $s$, cell $8+2a$ equal to the zero-extended unsigned word $m(a)$ for every natural $a$, and every other cell zero: each explicit source halt within any bound $t$ with memory $m'$ has a target acceptance within some $u\le C(t+s+1)(s+1)^d$ whose memory at $8+2a$ is the zero-extension of $m'(a)$ for every $a$; conversely every target halt with any verdict and memory within any bound $u$ is an acceptance and is matched by a source halt within some $t\le u$ preserving all those cells. For every signed-addressed program $P$ there likewise exist a natural-addressed program $Q$ and positive natural $C$, fixed before width and input, such that for every positive source width $s$ and arbitrary integer-addressed input $m$, the target at width $s+4$ starts with cell zero equal to $s$, source cell $a$ zero-extended into cell $8+2z(a)$, and other cells zero, where $z(a)=2a$ if $a\ge0$ and $z(-(j+1))=2j+1$ for $j\in\mathbb N$; each source halt within any bound $t$ with verdict $v$ and memory $m'$ has a target explicit halt within some $u\le C(t+s+1)(s+1)^d$ preserving every embedded source cell and recording $v$ as unsigned $0$ or $1$ in target cell $1$, and every target halt within any bound $u$ conversely arises from a source halt within some $t\le u$ with those same memory and verdict equalities. These operational clauses impose no support restriction on source memories and no requirement on other final target cells. To state the remaining clauses, a problem consists of instances at each natural size, an integer input list, a decision predicate, and a predicate on a natural-indexed integer output sequence. Say a program solves such a problem for natural parameters $\kappa,b$ and runtime function $T:\mathbb N\to\mathbb N$ when, for every natural size $n$, every instance whose input integers have absolute value at most $n^\kappa$, and every physical width at least $bL(n)$, it halts within $T(n)$ steps from position zero on the packed input $n$ followed by that input list, all words reduced modulo $2^W$, where $W$ is the physical bit width and every other cell initially zero, with the correct decision verdict and with the signed words immediately following the input satisfying the output predicate. Here $L(n)=\operatorname{log2}n+1$, with $\operatorname{log2}0=0$ and otherwise the floor of the base-two logarithm; signed-addressed widths may be any natural, including zero, while natural-addressed widths must be positive, its halt must be explicit, and its final cell zero must contain the verdict as unsigned $0$ or $1$. There is no upper width bound. (ii) For every problem $Q$ and every natural $K,q$ such that every size-$n$ input has length at most $B(n)=K(n+1)^q$ and the output predicate has the same truth value on every two integer sequences agreeing at all indices below $B(n)$, the following holds in both directions between the two machines: for every natural $\kappa$, source program $P$, natural $b$, and runtime function $T$, if $P$ solves $Q$ for those parameters, then there exist a target program $P'$, a natural $b'$, and positive natural $C$ solving the same $Q$ and $\kappa$ at all target widths at least $b'L(n)$ within $C(T(n)+B(n)+1)L(n)^d$ steps. Target witnesses may depend on $Q,K,q,\kappa,P,b,T$, but not on size, instance, or physical width; no growth hypothesis on $T$ is assumed. (iii) For every such $Q,K,q$ and every rational threshold $R>q$, a signed-addressed solver exists at some rational exponent below $R$ if and only if a natural-addressed solver exists at some rational exponent below $R$. In this statement and the remaining assertions, existence at exponent $r=p/e$ in reduced form with $e>0$ means: for every natural $\kappa$ there exist a program, natural $b$, and runtime function $T$ solving for those parameters, and some natural $A$ such that $T(n)^e\le A n^{\max(p,0)}$ for every $n\ge2$. Thus the exponent is fixed before $\kappa$, but the other witnesses may depend on $\kappa$; negative numerators are truncated to zero. (iv) Existence at some rational exponent strictly below $3$ is equivalent for the two machines for the following all-pairs-shortest-path problem: a size-$n$ instance is an integer-weighted directed graph on $\{0,\ldots,n-1\}$ in which every closed finite walk has nonnegative weight, walks may repeat vertices, and the empty walk has weight zero; input is the row-major edge-presence matrix followed by the row-major weights, with zero weights for absent edges. The decision predicate is always true; the empty graph at $n=0$ has no required output pairs. For each ordered pair $(i,j)$, output positions $2(in+j)$ and $2(in+j)+1$ must either be $1$ and a realized walk weight no greater than every walk weight from $i$ to $j$, or have the first entry $0$ and there be no such walk; in the latter case the distance entry is unconstrained. (v) Existence at some rational exponent strictly below $2$ for the EndStatement signed-addressed machine, whose instruction, fuel, packed-input, signed-output and growth conventions are precisely the signed-addressed conventions just stated, is equivalent to existence below $2$ for the natural-addressed machine on the unchanged problem with size-$n$ instances $x:\{0,\ldots,n-1\}\to\mathbb Z$, input list $x(0),\ldots,x(n-1)$, and decision predicate that three pairwise distinct indices have values summing to zero; its output predicate is always true, and its decision predicate is false for $n<3$. All size quantifiers include $n=0,1$, all magnitude exponents include $\kappa=0$ with $0^0=1$, and width coefficients may be zero; correctness at sizes zero and one remains required although the growth inequality starts at two. In (ii) and (iii), $K=0$ forces empty input lists and output predicates independent of the output sequence; empty instance types make their instance conditions vacuous. The exponents witnessing the two sides of any equivalence need not agree, and no equivalence by itself asserts existence of a solver on either side.