One-Tape Simulation Normal Forms

As in the configuration-set construction of F3, separate finite-support functions inside ${\mathrm{\Gamma }}^{\mathbb{N}}$ to obtain $\mathcal{T}$, and take $Q\times \mathbb{N}\times \mathcal{T}$. These formulas use only the displayed sets and blank, so changing the direction codomain has no effect on their sethood. The graph of $t[h:=b]$ is the subset of $\mathbb{N}\times \mathrm{\Gamma }$ given by $(j=h\wedge c=b)\vee (j\mathrm{\ne }h\wedge c=t(j))$. Exactly one clause supplies exactly one value in $\mathrm{\Gamma }$ at each $j$, so this is a total function.

Put $F=\mathrm{supp}(t)$. If $h\in F$, then $F\cup \{h\}=F$ is finite. Otherwise take a bijection $e:n\to F$, available by finiteness; extending it by $e^{\mathrm{\prime }}(n)=h$ gives a bijection $n+1\to F\cup \{h\}$, since the new value is outside the old range. This also works for $F=\mathrm{\varnothing }$ and $n=0$. At every $j\mathrm{\notin }F\cup \{h\}$ the new value equals $t(j)=\bigsqcup$. Hence $\mathrm{supp}(t[h:=b])\subseteq F\cup \{h\}$ is finite by F4.

At a nonhalting state, totality supplies a unique $(p,b,D)$. Exactly one head clause applies, and it returns a natural, including the clamped value zero. Together with the unique updated tape from the preceding steps this gives exactly one successor in ${\mathcal{C}}_M$. For $D=L,R$ this is the ordinary step formula, and for $D=S$ the head is unchanged. At a halting state the explicit nonhalting condition fails, so there is no successor.

Define $T:{\mathcal{C}}_M\to {\mathcal{C}}_M$ by this successor on nonhalting configurations and by $T(X)=X$ on halting ones. Its graph consists of these two disjoint prescriptions and is a set; it is total by the preceding step. F5 with $A={\mathcal{C}}_M$, $a=C$, $f=T$ supplies a unique $u:\mathbb{N}\to {\mathcal{C}}_M$ satisfying $u(0)=C$ and $u(i+1)=T(u(i))$.

Every nonempty set $B$ of natural indices has a least member: take one $b\in B$ and inspect the finite list $0,\dots ,b$. More formally, induction on $n$ proves that $B\cap \{0,\dots ,n\}$ is empty or has a least member. At zero it is empty or $\{0\}$. On adjoining $n+1$, retain the old least member if there was one; otherwise the new intersection is empty or $\{n+1\}$. At $n=b$ it is nonempty, and its least member is also least in $B$, because every index outside this initial list exceeds $b$. Thus, if $u$ ever halts, its first halting index $t$ exists.

If such $t$ exists, all $u(i)$ for $i<t$ are nonhalting, so $u(0),\dots ,u(t)$ is a genuine finite maximal run. Otherwise every transition of $u$ is genuine and $u$ is an infinite maximal run. For any other run with the same start, equality holds at index zero; whenever both prefixes continue, equal nonhalting configurations have equal successors by uniqueness. Induction gives agreement at every common index. A finite maximal run cannot end earlier, since the corresponding $u(i)$ would be nonhalting, and cannot continue past $t$, where there is no successor. An infinite run cannot pass a finite $t$ either. This proves uniqueness and the exhaustive, disjoint accept/reject/diverge alternatives. The constant tail of $u$ after $t$ is never part of a computation.

For any input $w:m\to \mathrm{\Sigma }$, the initial tape prescription assigns a unique value in $\mathrm{\Gamma }$ at each index. Its support is exactly $\{0,\dots ,m-1\}=m$: blank exclusion makes every input cell nonblank and every other cell blank. Thus $I_M(w)$ is a configuration. When $m=0$ the support is empty; when $m=1$ it is $\{0\}$. If $\mathrm{\Sigma }=\mathrm{\varnothing }$ only the empty input exists, and $\mathrm{\Gamma }=\{\bigsqcup \}$ is allowed. The start is nonhalting because the designated states are pairwise distinct. For an arbitrary already-halting start, the unique maximal run has zero transitions. These cover the degenerate inputs without a choice function or a false infinite halting tail.

The state product exists by F4. By F5, $(p,0)=(q,1)$ would imply $0=1$, which is false by F7. Also $(p,e)=(q,e)$ implies $p=q$. Thus marked and unmarked copies are disjoint even when the original state objects themselves are pairs; the three unmarked designated states remain pairwise distinct.

Take a bijection $e:n\to Q$ by F3. The tagged states over its first $j$ values form a finite set, by induction on $j\le n$. For $j=0$ this set is empty with its empty bijection. To pass to $j+1$, append $(e(j),0)$ and then $(e(j),1)$; neither equals an earlier state, and they differ from each other by step 1.1 and injectivity of $e$. If $f:r\to A$ is a bijection and $x\mathrm{\notin }A$, the map agreeing with $f$ on $r$ and taking $r$ to $x$ is a bijection $r+1\to A\cup \{x\}$: old images stay distinct, the new image is fresh, and every target is old or $x$. Applying this twice proves the induction step. At $j=n$ the finite set is exactly $Q\times \{0,1\}$.

Every nonhalting simulator state is either $(q,0)$ with $q$ originally nonhalting, or $(p,1)$ for some $p\in Q$. The former has a unique original entry and exactly one of the two displayed replacement clauses applies. The latter has the displayed return entry for each scanned symbol. The cases are disjoint and exhaust all required entries; outputs have state in the product, symbol in $\mathrm{\Gamma }$ and direction in $\{L,R\}$. The only states with no entries are the two unmarked halting states. Along with finite control and the unchanged finite alphabets, these checks establish that $N$ is a legal ordinary machine.

Suppose $C=(q,h,t)$ is nonhalting and $\delta (q,t(h))=(p,b,D)$ with $D=L$ or $R$. The first clause writes $b$ at $h$, changes the state to $(p,0)$, and applies the same $H_D$ as $M$. Thus its successor is $((p,0),H_D(h),t[h:=b])=E(C^{\mathrm{\prime }})$. It is already unmarked, so no earlier positive time in this segment is unmarked. This includes $D=L,h=0$, where both heads remain zero.

For $D=S$, put $u=t[h:=b]$. The first simulator step is exactly $E(C){⊢}_N((p,1),h+1,u)$. Its state is marked and hence nonhalting, even if $p=q_{\mathrm{a}\mathrm{c}\mathrm{c}}$ or $q_{\mathrm{r}\mathrm{e}\mathrm{j}}$. Write $c=u(h+1)$. The forced return entry rewrites $c$ as $c$, so its updated tape $v$ has $v(h+1)=u(h+1)$ and $v(j)=u(j)$ for every other $j$; consequently $v=u$. The head is at a positive successor by F7, whose unique predecessor is $h$, so the return ends at $((p,0),h,u)=E(C^{\mathrm{\prime }})$. At $h=0$ the head trace is $0,1,0$. The symbol $c$ may be blank or any nonblank symbol; the whole tape equality used no assumption about it.

Conversely, an unmarked starting configuration has the unique form $E(q,h,t)$ by F5. If $q$ is halting it has no successor. Otherwise its unique original entry has direction $L$, $R$ or $S$. The first two give the one-step segment of step 4.1. The third gives the marked first state and forced unmarked second state of step 4.2, with no unmarked interior. There is no fourth case and no freedom to take a different return transition. Thus all and only the next-unmarked segments are precisely the claimed simulations, in both directions.

Regard $N$ also as an extended machine with no $S$ entries; its ordinary and extended steps coincide. F1 gives its maximal run as well as that of $M$. For formal counters use the set ${\mathcal{C}}_M\times \mathbb{N}\times \mathbb{N}$, starting at $(C,0,0)$. At a nonhalting $(X,k,s)$, take the unique successor $X^{\mathrm{\prime }}$ and send the triple to $(X^{\mathrm{\prime }},k+1,s)$ for an $L\mathrm{/}R$ entry and to $(X^{\mathrm{\prime }},(k+1)+1,s+1)$ for an $S$ entry. At a halting $X$, leave the whole triple fixed. This is a total self-map, so F3 constructs its iterates. Restrict to the genuine indices of the original maximal run. Their coordinates are $(C_i,k_i,s_i)$ and $s_i$ is exactly the running count of $S$ entries: it starts at zero and increases by one precisely at such entries. No fixed tail is counted as genuine steps.

At index zero $k_0=s_0=0$ and the simulator starts at $E(C_0)$. Suppose it has reached $E(C_i)$ and $M$ has a next step. F2 expands that step into precisely one simulator step for $L\mathrm{/}R$ or two for $S$, reaching $E(C_{i+1})$ at the recursively prescribed $k_{i+1}$. There is no halt inside that segment. Applying induction to these finite expansions gives equality at every reached boundary, and supplies every transition in each expansion. If the original ends, apply induction up to its last index; otherwise apply it on all naturals.

We prove $k_i=i+s_i$ by induction. At zero, $0+0=0$. In an $L\mathrm{/}R$ step, $k_{i+1}=k_i+1=(i+s_i)+1=(i+1)+s_i$, and $s_{i+1}=s_i$. In an $S$ step, $k_{i+1}=(k_i+1)+1=((i+s_i)+1)+1=(i+1)+(s_i+1)$, and $s_{i+1}=s_i+1$. Both identities follow by the two successor laws of F5. These are the only transition types, so the equation holds at every reached index.

Also $0\le s_i\le i$. Nonnegativity follows since $0+s_i=s_i$, a witness in F6. For the upper bound the base is $0\le 0$. If $s_i\le i$, an $L\mathrm{/}R$ step retains $s_i\le i\le i+1$, where the second inequality has witness one. An $S$ step gives $s_i+1\le i+1$ by F7. Thus induction proves the upper bound. To bound $k_i$, induction using F5 shows that for every fixed $s\le i$ and every $j$, $j+s\le j+i$: the base is $s\le i$, and adding one to both sides preserves order by F7 and converts them into $(j+1)+s$ and $(j+1)+i$. Take $j=i,s=s_i$. The lower bound $i\le i+s_i$ has witness $s_i$. Hence $i\le k_i\le i+i$.

For each reached $i$, the times $0\le j<k_i$ are partitioned by the first $i$ half-open segments $[k_r,k_{r+1})$, $r<i$. This follows by induction: at $i=0$ the interval is empty; appending $[k_i,k_{i+1})$ extends exactly to $[0,k_{i+1})$ with disjoint interiors, because $k_{i+1}$ is $k_i+1$ or $(k_i+1)+1$. By F8 the appended interval contains only its boundary $k_i$, and in the second case also $k_i+1$. Thus every covered time is either a macro boundary or the sole interior time of an $S$ macro. The latter has the marked nonhalting configuration calculated in F2.

If the original first halts at $t$, then at each boundary $k_i$ for $i<t$ its unmarked simulator copy is nonhalting. Every other time before $k_t$ is a nonhalting interior by the partition. At $k_t$ the simulator is $E(C_t)$ and is halting with exactly the same accept/reject designation, head and tape. Thus this is its first halt. Its time is $t+s_t$ and satisfies the stated bounds. This includes $t=0$, when the partition is empty and both configurations already halt.

If the original is infinite, fix any simulator time $j$. The boundary $k_{j+1}$ exists and satisfies $j<j+1\le k_{j+1}$ by the bounds. Hence the finite expansion through that boundary includes time $j$. The partition makes its configuration either the unmarked copy of a nonhalting original state or a marked interior state; in both cases it is nonhalting. Uniqueness of successors makes all these finite expansions agree where they overlap. Equivalently they agree with the unique identity-extended simulator sequence supplied by F1; every one of its times is nonhalting, so every transition is genuine. The simulator therefore diverges.

These implications are equivalences. If the simulator accepts, the original cannot be infinite by step 4.2 and cannot halt rejecting by step 4.1, so the exhaustive alternatives in F1 force original acceptance. The same argument exchanges acceptance and rejection. If the simulator diverges, step 4.1 rules out either finite original outcome, so the original diverges. The forward implications are already proved in steps 4.1 and 4.2.

For every input $w$, unchanged alphabets and blank give the same initial tape $t_w$, and the designated start of $N$ gives $I_N(w)=((q_0,0),0,t_w)=E(I_M(w))$. For the empty word both initial tapes are wholly blank. Applying step 5.1 to these starts proves equality of accepted-input sets and preservation of halting on every input, hence of recognition and decision. At a finite halt the tapes and heads are equal by step 4.1, so applying any fixed output-reading function to them gives equal outputs. Conversely an ordinary machine is already a stay-put machine using only $L\mathrm{/}R$, with identical steps and runs, proving both inclusions for the two language classes.