$\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } S \models \text{dec}(\phi)$ exactly when $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } S \models \phi$

$\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \text{dec}(\phi)$ has one fewer quantifier than $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \phi$

Constant functions can be expressed

The successor function can be expressed

Projection functions can be expressed, for instance by representing tuples of naturals by sequencing them delimited by the space character

Turing machines are closed under composition. First assume we’re working with turing machines which map $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \bb N^k$ to $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \bb N$, and also assume that we’re working with alphabet $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } S = \{ 0,1,\_ \}$. Now to encode the composition $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } h : n \mapsto f(g_1(n), \dots, g_k(n))$ we can do the following. WLOG assume that each $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_i$ uses only the subset $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k\bb N + i \subseteq \bb Z$ of the tape (this does not impact turing machine power). Now to run $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } h$, do the following. Accept an input number in binary format. Now ‘smear’ each input digit into eight copies along the substrates $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k\bb N + i$ we’ve allotted for the composees $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_i$. Now run $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_1$, then $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_2$, up through $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_k$. By restricting each $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_i$ to the substrate $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k\bb N + i$ we guarantee that no composee $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_i$ will interfere with another. The result will be a tape empty on the left side and containing $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k$ interlaced numbers on the right side. Read off the first number, copying it to the left side of the tape. Read off the second number, copying it, placing it next to the first number separated by a blank character. Repeat $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k$ times, and then zero out the right side of the tape. Move these numbers back to the right side of the tape, and zero out the left side. Now we have $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k$ numbers—the results of the $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g_i$s—on the tape; these form the input for $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } f$. Run $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } f$.

Turing machines are closed under minimization: take $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } f : \bb N^{k + 1} \to \bb N$. To produce its minimization $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g : \bb N^k \to \bb N$, create a turing machine that does the following. WLOG assume $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } f$ only runs on the right side of the tape. Have $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g$ accept $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } k$ numbers. The first thing that $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g$ does is copy them to the left side of the tape alongside a distinguished number initialized to zero. Then $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g$ proceeds as follows. Repeatedly it copies the numbers, including the distinguished number, from the left of the tape to the right and then executes $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } f$. If the result is zero, $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g$ clears the right side of the tape, copies the distingushed number, clears the left side of the tape, and halts. Otherwise, $\newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } \newcommand{\card}{ \t{cd} } \newcommand{\dcup}{ \sqcup } \newcommand{\tup}[1]{ \langle {#1} \rangle } \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } \newcommand{\tpar}[1]{ \left( {#1} \right) } \newcommand{\tbrak}[1]{ \left[ {#1} \right] } \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } \newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\pre}[1]{{ \small `{#1} }} \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } \newcommand{\dd}{ \ddn{} } \newcommand{\d}{ \dd{} } \newcommand{\dn}[1]{ \ddn{#1}{} } \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } \newcommand{\cat}[1]{{ \sf{#1} }} \newcommand{\yo}{よ} \newcommand{\apar}{ {-} } \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } g$ increments the distinguished number and repeats.