Turing completeness of prompting

## Abstract

Abstract Since the success of GPT, large language models (LLMs) have been revolutionizing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different prompts to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.

## 1 Introduction

The mainstream architecture of large language models (LLMs; e.g., OpenAI, ; Anthropic, ; Meta, ; Google, ) is Transformers (Vaswani et al., ). There has been a series of theoretical studies on Transformers under realistic abstractions (Pérez et al., ; Bhattamishra et al., ; Hahn, ; Pérez et al., ; Hao et al., ; Liu et al., ; Chiang et al., ; Merrill & Sabharwal, ; Roberts, ; Merrill & Sabharwal, ; ; Hou et al., ; Li et al., ).
For example, Pérez et al. () have shown that the class of all Transformers with $\operatorname{hardmax}$ attention is Turing-complete: for any computable function $\varphi\in\mathsf{TIME}_{1}(t(n))$, there exists a Transformer that computes $\varphi$ using $\mathrm{O}(t(n))$ chain-of-thought (CoT; Wei et al., ) steps and $\mathrm{O}(\log(n+t(n)))$ precision on length-$n$ inputs; Merrill & Sabharwal () have later improved the CoT complexity to $\mathrm{O}(t(n))$ for $\mathsf{TIME}(t(n))$ functions. These works have finely characterized the capacities and limits of Transformers under the classic *one-model-one-task* paradigm.

Nevertheless, existing theoretical studies fail to align with the *LLM prompting* practice, i.e., the *one-model-many-tasks* paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different *prompts* to perform different tasks. Since the success of GPT (Brown et al., ), the LLM prompting paradigm has revolutionized machine learning (Liu et al., ). For example, a bonus capability arising from prompting is zero-shot learning (Wei et al., ): when provided with suitable prompts, LLMs can even perform novel tasks that are not present in their training corpora. Such empirical success calls for a theoretical understanding of the LLM prompting paradigm:

*Fundamentally, how powerful is the LLM prompting paradigm?*

We answer this call and present the first theory on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact *Turing-complete*: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that prompting is not only universal but also *efficiently* universal: even though we only use a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers.

#### Main contributions.

Our main contributions are informally stated as follows:

- •
Expressive power. We show that prompting is Turing-complete: there exists a finite-size Transformer $\varGamma$ such that for any computable function $\varphi$, there exists a finite prompt $\boldsymbol{\pi}_{\varphi}$ such that for any input $\boldsymbol{x}$, the Transformer $\varGamma$ computes $\varphi(\boldsymbol{x})$ following the prompt $\boldsymbol{\pi}_{\varphi}$. Importantly, our constructed Transformer $\varGamma$ is independent of the function $\varphi$, the prompt $\boldsymbol{\pi}_{\varphi}$ is independent of the input $\boldsymbol{x}$, and the input $\boldsymbol{x}$ can be arbitrarily long.
- •
CoT complexity. Our $\varGamma$ can compute any $\mathsf{TIME}_{2}(t(n))$ function within $\mathrm{O}(t(n))$ CoT steps and can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(t(n)\log t(n))$ CoT steps for any length-$n$ input. Notably, our result shows that even a *single* Transformer can still achieve nearly the same CoT complexity as the class of *all* Transformers does.
- •
Precision complexity. Our constructed $\varGamma$ can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(\log(n+t(n)))$ bits of precision for any length-$n$ input. Notably, our result shows that even a *single* Transformer can still achieve the same precision complexity as the class of *all* Transformers does. In particular, $\varGamma$ can decide any $\mathsf{P}$ language within *log-precision*.

### 1.1 Related work

Existing theoretical studies on Transformers fall under the classic *one-model-one-task* paradigm: they need to construct different Transformers for different tasks. There are two lines of related work: (i) when at most $\mathrm{O}(1)$ CoT steps are allowed, it has been shown that Transformers are capable but far from Turing-complete (Hahn, ; Hao et al., ; Liu et al., ; Chiang et al., ; Merrill & Sabharwal, ; ); (ii) when more CoT steps are allowed, it has been shown that the expressive power of Transformers increases with the number of CoT steps (Pérez et al., ; Bhattamishra et al., ; Pérez et al., ; Roberts, ; Merrill & Sabharwal, ; Hou et al., ; Li et al., ). Besides that, there have recently been studies on the learnability (Malach, ; Grau-Moya et al., ) and the in-context learning capability (Akyürek et al., ; von Oswald et al., ; Zhang et al., ; Ahn et al., ; Vladymyrov et al., ). Nevertheless, no existing work studies the LLM prompting paradigm (i.e., the one-model-many-tasks paradigm). Our work is the first to bridge this gap to the best of our knowledge.

### 1.2 Technical overview

A core step of our proof is to construct a new *model of computation* (called $2$-PTMs) that can be easily encoded into a prompt using a finite alphabet. Furthermore, we show that $2$-PTMs are not only Turing-complete but also nearly as efficient as Turing machines.

###### Theorem (informal version of Theorem 4.1 ) .

Any $\mathsf{TIME}(t(n))$ function can be computed by a $2$-PTM within $\mathrm{O}(t(n)\log t(n))$ steps. ∎

Given any computable function $\varphi$, we encode its $2$-PTM into a prompt $\boldsymbol{\pi}_{\varphi}$. Then, it remains to construct a Transformer $\varGamma$ that can execute $2$-PTMs. Since it is known that Transformers without CoTs are not universal (Hahn, ), the Transformer $\varGamma$ needs to use CoT steps to execute $2$-PTMs. Specifically, we use CoT steps to record the execution steps of the $2$-PTM so that the Transformer can restore the state of the $2$-PTM at any step. This establishes the CoT complexity of $\varGamma$.

###### Corollary (informal version of Corollary 4.5 ) .

Our constructed $\varGamma$ can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(t(n)\log t(n))$ CoT steps.

To incorporate input $\boldsymbol{x}$ into computation, we use $\mathrm{O}(|\boldsymbol{x}|)$ CoT steps to emulate an *imaginary* process of writing the input $\boldsymbol{x}$ onto a tape of the $2$-PTM. This implies the precision complexity of $\varGamma$.

###### Corollary (informal version of Corollary 4.7 ) .

Our constructed $\varGamma$ can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(\log(n+t(n)))$ bits of precision.

Finally, we construct a decoder-only Transformer that achieves the desiderata above by leveraging *ReLU activation*, *layer normalization*, and *causal attention*.

###### Theorem (informal version of Theorem 4.1 ) .

###### Corollary (informal version of Corollary 4.5 ) .

###### Corollary (informal version of Corollary 4.7 ) .

## 2 Preliminaries

Let $\upepsilon$ denote the empty string. Given a finite alphabet $\varSigma$, let $\varSigma^{n}$ ($n\geq 0$) denote the set of length-$n$ strings over $\varSigma$, let $\varSigma^{*}:=\bigcup_{n\geq 0}\varSigma^{n}$ denote the set of all finite strings over $\varSigma$, let $\varSigma^{+}:=\bigcup_{n\geq 1}\varSigma^{n}$ denote the set of all non-empty finite strings over $\varSigma$, and let $\varSigma^{\upomega}$ denote the set of all countably infinite strings over $\varSigma$. Each symbol in $\varSigma$ is called a *token*. For a string $\boldsymbol{x}\in\varSigma^{*}$, let $|\boldsymbol{x}|$ denote the length of the string, and let $\boldsymbol{x}^{n}$ denote repeating the string $n$ times. For two strings $\boldsymbol{x},\boldsymbol{y}\in\varSigma^{*}$, let $\boldsymbol{x}\cdot\boldsymbol{y}$ denote their concatenation. Given a string $\boldsymbol{x}=x_{0}\cdot x_{1}\cdots x_{|\boldsymbol{x}|-1}\in\varSigma^{*}$, for an index $i\in\mathbb{Z}$, let $x_{i}$ denote the $(i\bmod|\boldsymbol{x}|)$-th token of $\boldsymbol{x}$; for indices $i,j\in\mathbb{Z}$ with $i\bmod|\boldsymbol{x}|\leq j\bmod|\boldsymbol{x}|$, let $\boldsymbol{x}_{i:j}$ denote the substring $x_{i\bmod|\boldsymbol{x}|}\cdot x_{(i\bmod|\boldsymbol{x}|)+1}\cdots x_{(j
\bmod|\boldsymbol{x}|)-1}$.

### 2.1 Theory of computation

#### Turing machines.

*Turing machines* (TMs; Turing, ) are an abstract model of computation that defines the notion of computability (Church, ; Kleene, ; Turing, ). An $m$-tape TM is defined by a septuple $(Q,q_{\text{start}},q_{\text{halt}},\varSigma,\textvisiblespace,m,\delta)$ where $Q$ is the finite set of states, $q_{\text{start}}\in Q$ is the initial state, $q_{\text{halt}}$ is the halting state, $\varSigma$ is the finite alphabet of the tapes, $\textvisiblespace\in\varSigma$ is the blank symbol, $m\in\mathbb{N}$ is the number of tapes, and $\delta:(Q\setminus\{q_{\text{halt}}\})\times\varSigma^{m}\rightharpoonup Q
\times(\varSigma\times\{\mathtt{L},\mathtt{S},\mathtt{R}\})^{m}$ is the transition function. See, e.g., Arora & Barak () for details. By the Church–Turing thesis (Church, ; Kleene, ; Turing, ), a function $\varphi:\operatorname{dom}\varphi\to\{\mathtt{0},\mathtt{1}\}^{*}$ is said to be *computable* if there exists a TM that computes $\varphi(\boldsymbol{x})$ for all inputs $\boldsymbol{x}\in\operatorname{dom}\varphi$.

Shannon () has shown that any TM $M$ over any alphabet can be simulated by a TM $M^{\prime}$ over the binary alphabet $\varSigma=\{\mathtt{0},\mathtt{1}\}$ with $\textvisiblespace=\mathtt{0}$ (although $M^{\prime}$ uses more states). Hence, we will assume that TMs have a binary alphabet for simplicity throughout this paper.

#### Time complexity.

Let $n$ denote the length of the input. A function $t(n):\mathbb{N}\to\mathbb{R}_{+}$ is said to be a *complexity function* iff $t(n)$ is non-decreasing and either $t(n)$ is a constant $>1$ or $t(n)\to\infty$ as $n\to\infty$. In this work, we refer to the time complexity as the the time complexity on a random-access machine (RAM) unless otherwise stated (e.g., when working with TMs). If $\Theta(t(n))$ is a complexity function, let $\mathsf{TIME}_{m}(t(n))$ denote the class of functions that can be computed by an $m$-tape TM within $\mathrm{O}(t(n))$ steps, let $\mathsf{TIME}(t(n)):=\bigcup{}_{m\geq 1}\mathsf{TIME}_{m}(t(n))$ denote the class of functions that can be computed by a TM within $\mathrm{O}(t(n))$ steps, and let $\mathsf{P}\subset\mathsf{TIME}(\operatorname{poly}(n))$ denote the class of (indicator functions of) languages that can be decided in polynomial time.

### 2.2 Neural networks

#### ReLU neural networks.

A ReLU neural network $\psi:\mathbb{R}^{e_{0}}\to\mathbb{R}^{e_{L}}$ is a composition $\psi:=\psi_{L-1}\circ\cdots\circ\psi_{0}$ of basic operations $\psi_{l}:\mathbb{R}^{e_{l}}\to\mathbb{R}^{e_{l+1}}$ ($l=0,\dots,L-1$) where each basic operation $\psi_{l}(\boldsymbol{z})$ ($\boldsymbol{z}\in\mathbb{R}^{e_{l}}$) is either an affine map $\psi_{l}(\boldsymbol{z}):=\boldsymbol{W}_{l}\boldsymbol{z}+\boldsymbol{b}_{l}$ ($\boldsymbol{W}_{l}\in\mathbb{R}^{e_{l+1}\times e_{l}}$, $\boldsymbol{b}_{l}\in\mathbb{R}^{e_{l+1}}$), an entry-wise ReLU activation $\psi_{l}(\boldsymbol{z}):=\max\{\boldsymbol{z},\boldsymbol{0}\}$ (Fukushima, ) with $e_{l+1}=e_{l}$, or a layer normalization $\psi_{l}(\boldsymbol{z}):=\frac{\boldsymbol{z}}{\|\boldsymbol{z}\|_{2}}1_{[
\boldsymbol{z}\neq\boldsymbol{0}]}$ (Ba et al., ) with $e_{l+1}=e_{l}$.

#### Decoder-only Transformers.

Mainstream LLMs are based on *decoder-only* Transformers (Radford et al., ). Given a finite token alphabet $\varSigma$, a decoder-only Transformer $\varGamma:\varSigma^{+}\to\varSigma$ (with greedy decoding) is a composition $\varGamma:=\operatorname*{\arg\max}\circ\varGamma_{\text{out}}\circ\varGamma_{
L-1}\circ\cdots\circ\varGamma_{0}\circ\varGamma_{\text{emb}}$ consists of an *embedding* layer $\varGamma_{\text{emb}}:\varSigma\to\mathbb{R}^{d}$, *causal-attention* Transformer layer $\varGamma_{l}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ ($l=0,\dots,L-1$), and an *output* layer $\varGamma_{\text{out}}:\mathbb{R}^{d}\to\mathbb{R}^{\varSigma}$. A *token embedding* is a map $\operatorname{emb}:\varSigma\to\mathbb{R}^{d}$, and a *positional encoding* is a map $\operatorname{pos}:\mathbb{N}\to\mathbb{R}^{d}$. Following the common practice (Vaswani et al., ), given the input token sequence $\boldsymbol{v}=v_{0}\cdots v_{|\boldsymbol{v}|-1}\in\varSigma^{+}$, the embedding layer $\varGamma_{\text{emb}}$ adds a positional encoding $\operatorname{pos}(i)$ to each token embedding $\operatorname{emb}(v_{i})$:

$$ $\displaystyle\boldsymbol{z}_{0,i}:=\operatorname{emb}(v_{i})+\operatorname{pos }(i),\qquad i=0,\dots,|\boldsymbol{v}|-1,$ (1) $$

where $\operatorname{pos}$ is a computable function. Following existing theoretical works (e.g., Pérez et al., ; Hao et al., ; Merrill & Sabharwal, ), we use $\operatorname{hardmax}$ attention as a realistic abstraction of $\operatorname{softmax}$. Given an $\mathbb{R}$ sequence $\boldsymbol{s}$, if the maximum value of $\boldsymbol{s}$ appears $t$ times, then we define $\operatorname{hardmax}_{i}(\boldsymbol{s}):=\frac{1}{t}$ if $s_{i}$ equals the maximum value and $\operatorname{hardmax}_{i}(\boldsymbol{s}):=0$ otherwise.
Each Transformer layer $\varGamma_{l}$ has $H_{l}$ *attention heads* followed by a ReLU neural network $\phi_{l}:\mathbb{R}^{d}\to\mathbb{R}^{d}$. Each attention head $k$ has a *query* map $\operatorname{qry}_{l,k}:\mathbb{R}^{d}\to\mathbb{R}^{d_{l,k}}$, a *key* map $\operatorname{qry}_{l,k}:\mathbb{R}^{d}\to\mathbb{R}^{d_{l,k}}$, a *value* map $\operatorname{val}_{l,k}:\mathbb{R}^{d}\to\mathbb{R}^{d}$, and a *similarity* map $\operatorname{sim}_{l,k}:\mathbb{R}\to\mathbb{R}$ ($k=0,\dots,H_{l}-1$), all of which are ReLU neural networks. The similarity scores between two tokens $v_{i}$ and $v_{j}$ are

$$ $\displaystyle s_{l,k,i,j}:=\operatorname{sim}_{l,k}(\operatorname{qry}_{l,k}( \boldsymbol{z}_{l,i})^{\mathsf{T}}\operatorname{key}_{l,k}(\boldsymbol{z}_{l,j })).$ (2) $$

A decoder-only Transformer layer $\varGamma_{l}$ is computed via *causal attention* and *residual connection*:

$$ $\displaystyle\boldsymbol{z}_{l+1,i}:=\boldsymbol{z}_{l,i}+\phi_{l}{\bigg{(}{ \sum_{k=0}^{H_{l}-1}\!\bigg{(}{\sum_{j=0}^{i}\operatorname{hardmax}_{j}(s_{l,k ,i,0},\dots,s_{l,k,i,i})}\operatorname{val}_{l,k}(\boldsymbol{z}_{l,j})}\bigg{ )}\!\bigg{)}}.$ (3) $$

The output token is greedily selected according to the final outputs of the last token $v_{|\boldsymbol{v}|-1}$:

$$ $\displaystyle\varGamma(\boldsymbol{v}):=\operatorname*{\arg\max}_{c\in \varSigma}\varGamma_{\text{out}}(\boldsymbol{z}_{L,|\boldsymbol{v}|-1})_{c},$ (4) $$

where the output layer $\varGamma_{\text{out}}$ is a ReLU neural network.

Figure: Algorithm 1 Autoregressive generation: $\operatorname{generate}_{\varGamma}(\boldsymbol{x})$

Given a Transformer $\varGamma$, let $\operatorname{generate}_{\varGamma}:\varSigma^{+}\to\varSigma^{+}\cup\varSigma
^{\upomega}$ denote autoregressive generation using $\varGamma$. Specifically, let $\boldsymbol{w}\in\varSigma^{+}$ denote the input sequence and $\boldsymbol{y}\in\varSigma^{*}$ the (current) output sequence. Initially, $\boldsymbol{y}$ is an empty string. In each generation step, we append $\varGamma(\boldsymbol{v}\cdot\boldsymbol{y})$ to $\boldsymbol{y}$. The generation process ends once the last token of $\boldsymbol{y}$ is a so-called *stop token* $\texttt{\$}\in\varSigma$, and we define $\operatorname{generate}_{\varGamma}(\boldsymbol{w}):=\boldsymbol{y}$ at last. It is possible that generation never ends, in which case we have $\boldsymbol{y}\in\varSigma^{\upomega}$. The autoregressive generation procedure is formally presented in Algorithm 1. A Transformer is said to use *log-precision* for a computable function $\varphi$ if the intermediate computation of all generation steps uses $\mathrm{O}(\log n)$ bits of precision for every length-$n$ input of function $\varphi$ (Merrill & Sabharwal, ).

## 3 Turing completeness of prompting

###### Theorem 3.1 (Turing completeness of prompting) .

There exist a finite alphabet $\varSigma$, a finite-size decoder-only Transformer $\varGamma:\varSigma^{+}\to\varSigma$, and coding schemes $\operatorname{tokenize}:\{\mathtt{0},\mathtt{1}\}^{*}\to\varSigma^{*}$ and $\operatorname{readout}:\varSigma^{*}\to\{\mathtt{0},\mathtt{1}\}^{*}$ with which prompting is Turing-complete: for every computable function $\varphi:\operatorname{dom}\varphi\to\{\mathtt{0},\mathtt{1}\}^{*}$ with $\operatorname{dom}\varphi\subseteq\{\mathtt{0},\mathtt{1}\}^{*}$, there exists a prompt $\boldsymbol{\pi}_{\varphi}\in\varSigma^{+}$ such that for every input $\boldsymbol{x}\in\operatorname{dom}\varphi$, $\operatorname{generate}_{\varGamma}(\boldsymbol{\pi}_{\varphi}\cdot
\operatorname{tokenize}(\boldsymbol{x}))$ computes a finite CoT, and

$$ $\displaystyle\operatorname{readout}(\operatorname{generate}_{\varGamma}( \boldsymbol{\pi}_{\varphi}\cdot\operatorname{tokenize}(\boldsymbol{x})))= \varphi(\boldsymbol{x}).$ (5) $$

Here, $\varSigma,\varGamma,\operatorname{tokenize},\operatorname{readout}$ are independent of $\varphi$; $\boldsymbol{\pi}_{\varphi}$ is independent of $\boldsymbol{x}$; and for any input $\boldsymbol{x}\in\{\mathtt{0},\mathtt{1}\}^{*}$, $\operatorname{tokenize}$ runs in $\mathrm{O}(|\boldsymbol{x}|)$ time, and $\operatorname{readout}$ runs in $\mathrm{O}(|\varphi(\boldsymbol{x})|)$ time.

Our Theorem 3.1 shows that prompting can enable a single Transformer to be universal and establishes a theoretical underpinning for prompt engineering in practice. Note that CoT is necessary for Turing completeness because it is known that Transformers without CoTs cannot even compute the parity function (Hahn, ). As a CoT typically contains more information than the answer $\varphi(\boldsymbol{x})$ alone, we need a map $\operatorname{readout}:\varSigma^{*}\to\{\mathtt{0},\mathtt{1}\}^{*}$ here to extract the answer, resembling the fact that humans need to read out the answer from the generated CoT.

Furthermore, to elucidate the technical non-triviality of our Theorem 3.1, we remark that our Theorem 3.1 has ruled out trivial possibilities:

- •
Memorization? It is impossible that the Transformer $\varGamma$ simply memorizes all computable functions, because there are *infinitely* many computable functions while $\varGamma$ has only a *finite* size (i.e., it has a *finite* number of *finite*-bit parameters).
- •
Self-answering? It is impossible that the prompt $\boldsymbol{\pi}_{\varphi}$ simply reveals the answers for all possible inputs, because there can be *infinitely* many inputs while the prompt is *finite*.
- •
Tautology? It is impossible that $\varGamma$ simply restates $\boldsymbol{\pi}_{\varphi}\cdot\operatorname{tokenize}(\boldsymbol{x})$ and lets $\operatorname{tokenize}$ or $\operatorname{readout}$ compute $\varphi(\boldsymbol{x})$ instead, because the time hierarchy theorem (Hartmanis & Stearns, ) implies that a computable function $\varphi$ in general can require more than $\Omega(\max\{|\boldsymbol{x}|,|\varphi(\boldsymbol{x})|\})$ time while $\operatorname{tokenize}$ and $\operatorname{readout}$ run in only $\mathrm{O}(|\boldsymbol{x}|)$ time and $\mathrm{O}(|\varphi(\boldsymbol{x})|)$ time, respectively.

Our proof of Theorem 3.1 is constructive. In the rest of this section, we will present the core constructions in our proof, including the prompt, the CoT steps, the input tokenizer, and the Transformer. Due to space limit, the complete proof is deferred to Appendix B.

###### Theorem 3.1 (Turing completeness of prompting) .

### 3.1 Construction of prompts

In this subsection, we show how to construct a prompt $\boldsymbol{\pi}_{\varphi}$ for any given computable function $\varphi$. The basic idea here is that we let the prompt encode a formal description of the function $\varphi$ and later construct a Transformer that can execute the description. The construction of the Transformer is deferred to Section 3.4.

As computability means that there exists a TM that computes $\varphi$, one might seek to encode the TM into the prompt. Unfortunately, a TM can have an unbounded number of states and an unbounded number of tapes, but we are only allowed to construct all prompts using a *single* finite alphabet $\varSigma$ and to execute all prompts using a *single* finite-size Transformer. Even though one can use sophisticated schemes to encode TMs (Turing, ), it remains highly non-trivial to construct a Transformer to efficiently execute such encoded TMs.

Hence, instead of working with TMs directly, here we want a model of computation that (i) can be easily encoded by a single finite alphabet, that (ii) is still Turing-complete, and that (iii) is nearly as efficient as TMs.
Although a possible approach is to use an imperative model of computation such as Wang machines (Wang, ) and Davis–Sigal–Weyuker’s Post–Turing machines (DSW-PTMs; Davis et al., ), it is still unknown how to efficiently simulate arbitrary TMs using Wang machines or Davis–Sigal–Weyuker’s Post–Turing machines. This suggests that these models of computation might not be the best candidate for constructing the prompt.

To fulfill our desiderata, we propose a new imperative model of computation that extends Wang machines and DSW-PTMs. Inspired by the Hennie–Stearns theorem (Hennie & Stearns, ), we let our model of computation use two bi-infinite tapes $\mathtt{A}$ and $\mathtt{B}$. Each tape has infinitely many cells over the binary alphabet $\{\mathtt{0},\mathtt{1}\}$ and a head pointing to a cell. We call this model *two-tape Post–Turing machines* ($2$-PTMs). A $2$-PTM is defined by a finite instruction sequence $\boldsymbol{\iota}=\langle\iota_{0},\iota_{1},\dots,\iota_{|\boldsymbol{\iota}
|-1}\rangle$ where each instruction $\iota_{j}$ $(0\leq j<|\boldsymbol{\iota}|)$ is one of the following:

- •
#: halt;
- •
$\tau\mathtt{L}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$): move the head for tape $\tau$ one cell left, and go to $\iota_{j+1}$;
- •
$\tau\mathtt{R}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$): move the head for tape $\tau$ one cell right, and go to $\iota_{j+1}$;
- •
$\tau\mathtt{0}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$): write $\mathtt{0}$ to the pointed cell of tape $\tau$, and go to $\iota_{j+1}$;
- •
$\tau\mathtt{1}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$): write $\mathtt{1}$ to the pointed cell of tape $\tau$, and go to $\iota_{j+1}$;
- •
$\tau\textnormal{{!}}_{k}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$; $k\neq j$): if the pointed cell of tape $\tau$ is $\mathtt{0}$, go to $\iota_{k}$; else, go to $\iota_{j+1}$;
- •
$\tau\textnormal{{?}}_{k}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$; $k\neq j$): if the pointed cell of tape $\tau$ is $\mathtt{1}$, go to $\iota_{k}$; else, go to $\iota_{j+1}$.

Let $\mathcal{I}$ denote the set of all possible instructions. Before execution, the input is written to tape $\mathtt{A}$, and the head for tape $\mathtt{A}$ is pointing to the leftmost cell of the input. All blank tape cells are filled with $\mathtt{0}$. Then, execution starts from instruction $\iota_{0}$ and halts upon instruction #, and the output is the content left on tape $\mathtt{A}$ starting from cell 0 0. We will show in Section 4.1 that $2$-PTMs are not only Turing-complete but also nearly as efficient as TMs.

Next, we describe how to construct a prompt for a given computable function. Recall that $2$-PTMs use the binary alphabet $\{\mathtt{0},\mathtt{1}\}$ with blank symbol being $\mathtt{0}$. To distinguish the input symbol $\mathtt{0}$ and the blank symbol $\mathtt{0}$, we employ Shannon’s encoding $S:\{\mathtt{0},\mathtt{1}\}^{*}\to\{\mathtt{0},\mathtt{1}\}^{*}$ (Shannon, ) to translate inputs and outputs of computable functions:

$$ $\displaystyle S(\upepsilon):=\upepsilon,\quad S(\mathtt{0}):=\mathtt{10},\quad S (\mathtt{1}):=\mathtt{11};$ (6) $\displaystyle S(\boldsymbol{x}):=S(x_{0})\cdots S(x_{|\boldsymbol{x}|-1}), \quad\boldsymbol{x}\in\{\mathtt{0},\mathtt{1}\}^{*}.$ (7) $$

Thus, we identify $\mathtt{00}$ as the blank symbol. Note that Shannon’s encoding $S$ is injective, and that both $S$ and its corresponding decoding $S^{-1}$ are computable in linear time. Since the class of $2$-PTMs is Turing-complete, then given any computable function $\varphi$, there exists a $2$-PTM $\boldsymbol{\iota}\in\mathcal{I}^{+}$ that computes $S(\varphi(\boldsymbol{x}))$ from $S(\boldsymbol{x})$ for all $\boldsymbol{x}\in\operatorname{dom}\varphi$. It remains to encode $\boldsymbol{\iota}$ into a prompt $\boldsymbol{\pi}_{\varphi}$.

We will define a map $P:\mathbb{N}\times\mathcal{I}\to\varSigma^{*}$ to encode each instruction $\iota_{j}$ and let the prompt be the concatenation of $P(j,\iota_{j})$, where the alphabet $\varSigma$ will be specified later. For instructions #, $\tau\mathtt{L}$, $\tau\mathtt{R}$, $\tau\mathtt{0},$ $\tau\mathtt{1}$, we can simply create a corresponding token in $\varSigma$ for each of them:

$$ $\displaystyle P(j,\iota_{j}):=\iota_{j}\qquad\text{if }\iota_{j}\text{ is one of $\texttt{\#}$, $\tau\mathtt{L}$, $\tau\mathtt{R}$, $\tau\mathtt{0},$ $\tau \mathtt{1}$}.$ (8) $$

For instructions $\tau\textnormal{{!}}_{k}$ and $\tau\textnormal{{?}}_{k}$, since $k$ can be any natural number, we can no longer create a token for each $k$ because otherwise the alphabet $\varSigma$ would be infinite. Instead, to help the Transformer to execute the prompt, we use a unary encoding w.r.t $k-j$:

$$ $\displaystyle P(j,\iota_{j}):=\begin{cases}\tau{\texttt{!}}\cdot\texttt{-}^{j- k}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{\texttt{!}}_{k}\text{ and }k<j;\\ \tau{\texttt{!}}\cdot\texttt{+}^{k-j}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{!}}_{k}\text{ and }k>j;\\ \tau{\texttt{?}}\cdot\texttt{-}^{j-k}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{?}}_{k}\text{ and }k<j;\\ \tau{\texttt{?}}\cdot\texttt{+}^{k-j}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{?}}_{k}\text{ and }k>j;\end{cases}$ (9) $$

where we create seven auxiliary tokens $\mathtt{A}\texttt{!},\mathtt{B}\texttt{!},\mathtt{A}\texttt{?},\mathtt{B}
\texttt{?},\texttt{-},\texttt{+},\texttt{@}\in\varSigma$ to be used by the Transformer. Finally, we construct the prompt as

$$ $\displaystyle\boldsymbol{\pi}_{\varphi}:=\texttt{\textasciicircum}\cdot P(0, \iota_{0})\cdots P(|\boldsymbol{\iota}|-1,\iota_{|\boldsymbol{\iota}|-1})\cdot \texttt{\textdollar},$ (10) $$

where we create two auxiliary tokens $\texttt{\textasciicircum},\texttt{\textdollar}\in\varSigma$ to be used by the Transformer.

Example. A $2$-PTM for deciding the Dyck language (Schützenberger, ) is(^1^11From now on, we will omit delimiters for conciseness when there is no ambiguity.)

and its corresponding prompt is

### 3.2 Recording execution in CoT steps

It is known that finite-size Transformers without CoT steps are not universal (Hahn, ). To achieve Turing completeness, here we make use of CoT steps to record execution steps of the $2$-PTM $\boldsymbol{\iota}$ so that the Transformer can restore the state of the $2$-PTM at any execution step. In this subsection, we focus on the case where the input is empty; we will describe how to incorporate the input in Section 3.3.

Let $\iota_{j}$ denote the current instruction, and let $c_{\mathtt{A}},c_{\mathtt{B}}$ denote the pointed cell of tapes $\mathtt{A}$ and $\mathtt{B}$, respectively. Note that each execution step can be summarized as a quadruple $(j,\iota_{j},c_{\mathtt{A}},c_{\mathtt{B}})$, where $\iota_{j}$ is the current instruction, and $c_{\mathtt{A}}$ and $c_{\mathtt{B}}$ are the currently pointed cell of tapes $\mathtt{A}$ and $\mathtt{B}$, respectively. We will define a map $C:\mathbb{N}\times\mathcal{I}\times\{\mathtt{0},\mathtt{1}\}^{2}\to\varSigma^{*}$ that maps each execution step to one or more CoT steps. If $\iota_{j}$ is one of #, $\tau\mathtt{L}$, $\tau\mathtt{R}$, $\tau\mathtt{0}$, $\tau\mathtt{1}$, we simply use a single CoT step to record $\iota_{j}$:

$$ $\displaystyle C(j,\iota_{j},c_{\mathtt{A}},c_{\mathtt{B}}):=\iota_{j}\qquad \text{if }\iota_{j}\text{ is one of $\texttt{\#}$, $\tau\mathtt{L}$, $\tau \mathtt{R}$, $\tau\mathtt{0},$ $\tau\mathtt{1}$}.$ (11) $$

If $\iota_{j}$ is $\tau\texttt{!}_{k}$ or $\tau\texttt{?}_{k}$, we record whether the go-to condition is satisfied or not:

$$ $\displaystyle C(j,\iota_{j},c_{\mathtt{A}},c_{\mathtt{B}}):=\begin{cases} \texttt{/}&\text{if }\iota_{j}=\tau{\texttt{!}}_{k}\text{ and }c_{\tau}\neq \mathtt{0};\\ {\texttt{=}}\cdot\texttt{-}^{j-k}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{!}}_{k},\text{ }c_{\tau}=\mathtt{0},\text{ and }k<j;\\ {\texttt{=}}\cdot\texttt{+}^{k-j}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{!}}_{k},\text{ }c_{\tau}=\mathtt{0},\text{ and }k>j;\\ \texttt{/}&\text{if }\iota_{j}=\tau{\texttt{?}}_{k}\text{ and }c_{\tau}\neq \mathtt{1};\\ {\texttt{=}}\cdot\texttt{-}^{j-k}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{?}}_{k},\text{ }c_{\tau}=\mathtt{1},\text{ and }k<j;\\ {\texttt{=}}\cdot\texttt{+}^{k-j}\cdot\texttt{@}&\text{if }\iota_{j}=\tau{ \texttt{?}}_{k},\text{ }c_{\tau}=\mathtt{1},\text{ and }k>j;\end{cases}$ (12) $$

where we create two auxiliary tokens $\texttt{/},\texttt{=}\in\varSigma$ to indicate whether the go-to condition is unsatisfied or satisfied, respectively.
The execution step stops once it reaches the halting instruction #.

Finally, we append the output $\varphi(\boldsymbol{x})$ after the execution steps in the CoT. We create a new auxiliary token $\texttt{:}\in\varSigma$ to mark the beginning of the output and reuse the token $\texttt{\textdollar}\in\varSigma$ to mark the end of the output, and we put the output $\varphi(\boldsymbol{x})\in\{\mathtt{0},\mathtt{1}\}^{*}\subseteq\varSigma^{*}$ between : and $. Hence, we define $\operatorname{readout}$ as extracting the part of the CoT between : and $ (see Algorithm 2). By construction, the number of CoT steps is proportional to the number of execution steps plus the length of the output.

Figure: Algorithm 2 Extracting output from CoT ($\operatorname{readout}$)

Example (cont’d). An empty input $\upepsilon$ is in the Dyck language. Its corresponding CoT steps are:

$$ $\displaystyle\texttt{/}\mathtt{A}\mathtt{0}\mathtt{A}\mathtt{L}\mathtt{A} \mathtt{0}\mathtt{A}\mathtt{L}\texttt{/}\mathtt{A}\mathtt{R}\mathtt{A}\mathtt{ R}\mathtt{A}\mathtt{1}\mathtt{A}\mathtt{R}\mathtt{B}\mathtt{L}\texttt{/} \mathtt{A}\mathtt{1}\texttt{:}\mathtt{1}\texttt{\textdollar}.$ $$

To recap, we have created a finite alphabet of 23 tokens all together:

$$ $\displaystyle\varSigma:=\{\texttt{\#},\mathtt{A}\mathtt{L},\mathtt{B}\mathtt{L },\mathtt{A}\mathtt{R},\mathtt{B}\mathtt{R},\mathtt{A}\mathtt{0},\mathtt{B} \mathtt{0},\mathtt{A}\mathtt{1},\mathtt{B}\mathtt{1},\mathtt{A}\texttt{!}, \mathtt{B}\texttt{!},\mathtt{A}\texttt{?},\mathtt{B}\texttt{?},\texttt{-}, \texttt{+},\texttt{@},\texttt{\textasciicircum},\texttt{\textdollar},\texttt{/ },\texttt{=},\texttt{:},\mathtt{0},\mathtt{1}\}.$ (13) $$

### 3.3 Construction of input tokenizer

In this subsection, we describe our input tokenizer $\operatorname{tokenize}:\{\mathtt{0},\mathtt{1}\}^{*}\to\varSigma^{*}$, which is independent of the function $\varphi$ and can encode any input $\boldsymbol{x}\in\{\mathtt{0},\mathtt{1}\}^{*}$ without changing the prompt $\boldsymbol{\pi}_{\varphi}$. Although it is possible to introduce additional auxiliary tokens to represent inputs, here we provide a simpler construction that makes use of only the existing tokens in $\varSigma$.

The key idea here is to use CoT steps to emulate an imaginary process of writing the input to tape $\mathtt{A}$. We will define a map $E:\{\mathtt{0},\mathtt{1}\}^{+}\to\varSigma^{+}$ that encodes an input $\boldsymbol{x}$ into CoT steps. Since $2$-PTMs assume that the head for tape $\mathtt{A}$ is initially pointing to the leftmost cell of the input, we write the input from right to left onto tape $\mathtt{A}$. Hence, for each bit $x_{i}$ of the input $\boldsymbol{x}$, we write its Shannon encoding $S(x_{i})$ from right to left onto tape $\mathtt{A}$:

$$ $\displaystyle E(\mathtt{0}):=\mathtt{A}\mathtt{L}\mathtt{A}\mathtt{L}\mathtt{A }\mathtt{1},\qquad E(\mathtt{1}):=\mathtt{A}\mathtt{L}\mathtt{A}\mathtt{1} \mathtt{A}\mathtt{L}\mathtt{A}\mathtt{1}.$ (14) $$

For the entire input, we concatenate the CoT steps of each bit from right to left:

$$ $\displaystyle E(\boldsymbol{x}):=E(x_{|\boldsymbol{x}|-1})\cdots E(x_{0}), \qquad\boldsymbol{x}\in\{\mathtt{0},\mathtt{1}\}^{+}.$ (15) $$

Intuitively, $E(\boldsymbol{x})$ represents execution steps of an imaginary program that writes $S(\boldsymbol{x})$ onto tape $\mathtt{A}$.

To ensure that the tape-$\mathtt{A}$ head is at cell 0 0 after writing the input, we first move the tape-$\mathtt{A}$ head $|S(\boldsymbol{x})|=2|\boldsymbol{x}|$ steps right. Hence, we define the CoT steps for writing $S(\boldsymbol{x})$ as $Z:\{\mathtt{0},\mathtt{1}\}^{+}\to\varSigma^{+}$,

$$ $\displaystyle Z(\boldsymbol{x}):=\mathtt{AR}^{2|\boldsymbol{x}|}\cdot E( \boldsymbol{x}),\qquad\boldsymbol{x}\in\{\mathtt{0},\mathtt{1}\}^{+}.$ (16) $$

Nevertheless, there is a caveat: a $2$-PTM should start from $\iota_{0}$, but these extra CoT steps $Z(\boldsymbol{x})$ will confuse the Transformer into starting from $\iota_{|Z(\boldsymbol{x})|}$. To address this caveat, our input tokenizer $\operatorname{tokenize}$ additionally employs an imaginary go-to step to let the Transformer go back to $\iota_{0}$. Following Equation (12), we re-use $\texttt{=},\texttt{-},\texttt{@}$ to construct the imaginary go-to step:

$$ $\displaystyle\operatorname{tokenize}(\boldsymbol{x}):=\begin{cases}\upepsilon& \text{if }\boldsymbol{x}=\upepsilon,\\ Z(\boldsymbol{x})\cdot\texttt{=}\cdot{\texttt{-}}^{|Z(\boldsymbol{x})|}\cdot \texttt{@}&\text{if }\boldsymbol{x}\neq\upepsilon.\end{cases}$ (17) $$

Example. Since input $\mathtt{01}$ has Shannon encoding $S(\mathtt{01})=\mathtt{1011}$, it is tokenized as

$$ $\displaystyle\operatorname{tokenize}(\mathtt{01})=\mathtt{A}\mathtt{R}\mathtt{ A}\mathtt{R}\mathtt{A}\mathtt{R}\mathtt{A}\mathtt{R}\mathtt{A}\mathtt{L} \mathtt{A}\mathtt{1}\mathtt{A}\mathtt{L}\mathtt{A}\mathtt{1}\mathtt{A}\mathtt{ L}\mathtt{A}\mathtt{L}\mathtt{A}\mathtt{1}\texttt{=}\texttt{-}\texttt{-} \texttt{-}\texttt{-}\texttt{-}\texttt{-}\texttt{-}\texttt{-}\texttt{-}\texttt{ -}\texttt{-}\texttt{@}.$ $$

### 3.4 Construction of Transformer

In this subsection, we sketch how to construct a decoder-only Transformer $\varGamma$ that executes prompts through CoT steps as described in Section 3.2. This means that we need to execute $2$-PTMs using *ReLU activation*, *layer normalization*, and *causal attention*. Due to the space limit, we only present three core operations to be used by $\varGamma$ here and defer the detailed construction to Appendix B.

#### Boolean algebra via ReLU activation.

Let $\operatorname{ReLU}(z):=\max\{z,0\}$ denote the ReLU function. Boolean algebra is a basic building block of our Transformer for, e.g., checking the go-to condition. A core operation in Boolean algebra is the $\land$ operation. Here, we implement $\land$ via ReLU activation:

$$ $\displaystyle u\land v=\operatorname{ReLU}(u+v-1),\qquad u,v\in\{0,1\}.$ (18) $$

Together with negation $\neg v=1-v$, they can implement all other Boolean operations such as $u\lor v=\neg((\neg u)\land(\neg v))$ and $u\oplus v=(u\land(\neg v))+((\neg u)\land v)$.

#### Equality check via layer normalization.

Let $\operatorname{LN}(\boldsymbol{z}):=\frac{\boldsymbol{z}}{\|\boldsymbol{z}\|_{2
}}1_{[\boldsymbol{z}\neq\boldsymbol{0}]}$ denote layer normalization (LN). When checking whether a tape cell has been written or not, we will need an equality check between two real numbers: $\operatorname{Equal}:\mathbb{R}^{2}\to\{0,1\}$ where $\operatorname{Equal}(u,v):=1_{[u=v]}$ ($u,v\in\mathbb{R}$). Since $\operatorname{Equal}$ is not a continuous map, it cannot be implemented using only affine maps or ReLU activation. Instead, we implement $\operatorname{Equal}$ via layer normalization as follows:

$$ $\displaystyle\operatorname{Equal}(u,v):=\operatorname{ReLU}(\operatorname{LN}( u-v))+\operatorname{ReLU}(\operatorname{LN}(v-u)),\qquad u,v\in\mathbb{R}.$ (19) $$

#### Farthest retrieval via causal attention.

A core operation to be used by the Transformer $\varGamma$ can be abstracted as follows: Given a sequence of values $\boldsymbol{v}=\langle v_{0},\ldots,v_{|\boldsymbol{v}|-1}\rangle$ with $v_{i}\in\{-1,0,+1\}$ for all $i$, find the *smallest* $i$ such that $\sum_{j=0}^{i}v_{j}=\sum_{j=0}^{|\boldsymbol{v}|-1}v_{j}$. However, since causal attention is an average rather than a sum, it cannot even compute the sum $\sum_{j=0}^{i}v_{j}$ for any $i$. It can compute the average $\frac{1}{i+1}\sum_{j=0}^{i}v_{j}$ for every $i$, but $\sum_{j=0}^{i}v_{j}=\sum_{j=0}^{|\boldsymbol{v}|-1}v_{j}$ does not mean $\frac{1}{i+1}\sum_{j=0}^{i}v_{j}=\frac{1}{|\boldsymbol{v}|}\sum_{j=0}^{|
\boldsymbol{v}|-1}v_{j}$. To bypass the mismatched coefficients $\frac{1}{i+1}$ and $\frac{1}{|\boldsymbol{v}|}$, we use LN to remove the averaging coefficient $\frac{1}{i+1}$. First, we let every token attend to the initial token ^ at $i=0$ to compute $\frac{1}{i+1}$ and compute

$$ $\displaystyle\boldsymbol{u}_{i}:=\operatorname{LN}\!\bigg{(}\frac{\sum_{j=0}^{ i}v_{j}}{i+1},\frac{1}{i+1}\bigg{)}^{\mathsf{T}}=\Bigg{(}\frac{\sum_{j=0}^{i}v _{j}}{\sqrt{(\sum_{j=0}^{i}v_{j})^{2}+1}},\frac{1}{\sqrt{(\sum_{j=0}^{i}v_{j}) ^{2}+1}}\Bigg{)}^{\mathsf{T}}.$ (20) $$

If $\sum_{j=0}^{i}v_{j}=\sum_{j=0}^{|\boldsymbol{v}|-1}v_{j}$, we have $\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}=1$; if $\sum_{j=0}^{i}v_{j}\neq\sum_{j=0}^{|\boldsymbol{v}|-1}v_{j}$, we have $\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}<1$. Thus, we can add $\boldsymbol{u}_{|\boldsymbol{v}|-1}$ to the query map $\operatorname{qry}$ and add $\boldsymbol{u}_{i}$ to the key map $\operatorname{key}$ in attention to retrieve an $i$ with $\sum_{j=0}^{i}v_{j}=\sum_{j=0}^{|\boldsymbol{v}|-1}v_{j}$.

It remains to retrieve the *smallest* such $i$ via causal attention. Since $\sum_{j=0}^{i}v_{i}\leq i+1\leq|\boldsymbol{v}|$, then note that if $\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}<1$, we in fact have

$$ $\displaystyle\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}$ $\displaystyle<\bigg{(}\frac{|\boldsymbol{v}|}{\sqrt{|\boldsymbol{v}|^{2}+1}}, \frac{1}{\sqrt{|\boldsymbol{v}|^{2}+1}}\bigg{)}\bigg{(}\frac{|\boldsymbol{v}|+ 1}{\sqrt{(|\boldsymbol{v}|+1)^{2}+1}},\frac{1}{\sqrt{(|\boldsymbol{v}|+1)^{2}+ 1}}\bigg{)}^{\mathsf{T}}$ (21) $\displaystyle=\frac{|\boldsymbol{v}|(|\boldsymbol{v}|+1)+1}{\sqrt{|\boldsymbol {v}|^{2}+1}\sqrt{(|\boldsymbol{v}|+1)^{2}+1}}=1-\Omega\Big{(}\frac{1}{| \boldsymbol{v}|^{4}}\Big{)}.$ (22) $$

This motivates us to use the following quantity, which can be computed in positional encoding $\operatorname{pos}$:

$$ $\displaystyle p_{i}:=1-\frac{(i+1)(i+2)+1}{\sqrt{(i+1)^{2}+1}\sqrt{(i+2)^{2}+1 }}=\Omega\Big{(}\frac{1}{(i+1)^{4}}\Big{)}.$ (23) $$

Note that if $\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}=1$ and $\boldsymbol{u}_{j}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}<1$, we also have

$$ $\displaystyle\boldsymbol{u}_{j}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1 }+\frac{p_{|\boldsymbol{v}|-1}}{j+1}\leq\boldsymbol{u}_{j}^{\mathsf{T}} \boldsymbol{u}_{|\boldsymbol{v}|-1}+p_{|\boldsymbol{v}|-1}<1=\boldsymbol{u}_{i }^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}<\boldsymbol{u}_{i}^{\mathsf{ T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}+\frac{p_{|\boldsymbol{v}|-1}}{i+1}.$ (24) $$

Therefore, we can retrieve the smallest $i$ with $\boldsymbol{u}_{i}^{\mathsf{T}}\boldsymbol{u}_{|\boldsymbol{v}|-1}=1$ using query vector $(\boldsymbol{u}_{|\boldsymbol{v}|-1},p_{|\boldsymbol{v}|-1})^{\mathsf{T}}$ and key vector $(\boldsymbol{u}_{i},\frac{1}{i+1})^{\mathsf{T}}$ in causal attention.

## 4 Complexity bounds

In this section, we (i) show in Section 4.1 that our $2$-PTMs are Turing-complete and nearly as efficient as TMs and (ii) use this result to characterize the complexities of our constructed $\varGamma$ in Sections 4.2 & 4.3. Throughout this section, we let $t(n)$ denote a complexity function. Following the convention in complexity theory, we allow different computable functions to have different constant factors in the big $\mathrm{O}$ notation.

### 4.1 Efficient simulation of TMs by 2 2 2 2 -PTMs

Since $2$-PTMs are an essential component of our construction, we need the complexity bounds of $2$-PTMs to analyze the complexities of $\varGamma$. While Wang machines and DSW-PTMs suffer from a polynomial slowdown over TMs (Neary et al., ), we show that our $2$-PTMs in fact has only at most a logarithmic slowdown over TMs.

###### Theorem 4.1 (efficient simulation) .

$\mathsf{TIME}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n)\log t(n))$.

Theorem 4.1 shows that our $2$-PTMs are Turing-complete and nearly as efficient as TMs. To prove it, we need the following Lemma 4.2 to establish an equivalence between two-tape TMs and $2$-PTMs.

###### Lemma 4.2 (two-tape simulation) .

$\mathsf{TIME}_{2}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))$.

###### Proof sketch of Lemma 4.2 .

For any computable function $\varphi\in\mathsf{TIME}_{2}(t(n))$, there exists a two-tape TM $M=(Q,q_{\text{start}},q_{\text{halt}},\{\mathtt{0},\mathtt{1}\},
\textvisiblespace=\mathtt{0},m=2,\delta)$ that computes $S(\varphi(\boldsymbol{x}))$ from $S(\boldsymbol{x})$ within time $\mathrm{O}(t(n))$, according to Shannon (). Suppose w.l.o.g. that $Q=\{0,1,\dots,K\}$ ($K\in\mathbb{N}_{+}$) and that $q_{\text{start}}=0$, $q_{\text{halt}}=K$. We will construct a $2$-PTM $\boldsymbol{\iota}$ of length $|\boldsymbol{\iota}|=27K+1$ that simulates $M$ within time $\mathrm{O}(t(n))$.

Recall that $\delta:(Q\setminus\{q_{\text{halt}}\})\times\{\mathtt{0},\mathtt{1}\}^{2}\to Q
\times(\{\mathtt{0},\mathtt{1}\}\times\{\mathtt{L},\mathtt{S},\mathtt{R}\})^{2}$. We use exactly six instructions $\boldsymbol{\eta}_{(q^{\prime},c_{\mathtt{A}},d_{\mathtt{A}},c_{\mathtt{B}},d_
{\mathtt{B}})}$ to simulate each transition $(q^{\prime},c^{\prime}_{\mathtt{A}},d_{\mathtt{A}},c^{\prime}_{\mathtt{B}},d_{
\mathtt{B}})$, where $q^{\prime}\in Q$, $c^{\prime}_{\mathtt{A}},c^{\prime}_{\mathtt{B}}\in\{\mathtt{0},\mathtt{1}\}$, $d_{\mathtt{A}},d_{\mathtt{B}}\in\{\mathtt{L},\mathtt{S},\mathtt{R}\}$. If $d_{\mathtt{A}},d_{\mathtt{B}}\neq\mathtt{S}$, we let

$$ $\displaystyle\boldsymbol{\eta}_{(q^{\prime},c^{\prime}_{\mathtt{A}},d_{\mathtt {A}},c^{\prime}_{\mathtt{B}},d_{\mathtt{B}})}:=\langle\mathtt{A}c^{\prime}_{ \mathtt{A}},\mathtt{A}{d_{\mathtt{A}}},\mathtt{B}c^{\prime}_{\mathtt{B}}, \mathtt{B}{d_{\mathtt{B}}},\mathtt{A}\texttt{!}_{27q^{\prime}},\mathtt{A} \texttt{?}_{27q^{\prime}}\rangle.$ (25) $$

If $d_{\mathtt{A}}=\mathtt{S}$ or $d_{\mathtt{B}}=\mathtt{S}$, we can replace the corresponding $\mathtt{A}d_{\mathtt{A}}$ or $\mathtt{B}d_{\mathtt{B}}$ with $\mathtt{A}c^{\prime}_{\mathtt{A}}$ or $\mathtt{B}c^{\prime}_{\mathtt{B}}$, respectively, so $\boldsymbol{\eta}_{(q^{\prime},c^{\prime}_{\mathtt{A}},d_{\mathtt{A}},c^{
\prime}_{\mathtt{B}},d_{\mathtt{B}})}$ still has exactly six instructions.

Then for each $q\in Q\setminus\{q_{\text{halt}}\}$, we use 27 instructions to simulate its transition rules:

$$ $\displaystyle\boldsymbol{\iota}_{27q:27q+27}:=\langle\mathtt{A}\texttt{?}_{27q +14},\mathtt{B}\texttt{?}_{27q+8},\boldsymbol{\eta}_{\delta(q,\mathtt{0}, \mathtt{0})},\boldsymbol{\eta}_{\delta(q,\mathtt{0},\mathtt{1})},\mathtt{B} \texttt{?}_{27q+21},\boldsymbol{\eta}_{\delta(q,\mathtt{1},\mathtt{0})}, \boldsymbol{\eta}_{\delta(q,\mathtt{1},\mathtt{1})}\rangle.$ (26) $$

For the halting state $q_{\text{halt}}=K$, we use one instruction $\iota_{27K}:=\texttt{\#}$ to simulate it.

Since $\boldsymbol{\iota}$ simulates each transition of $M$ by $\mathrm{O}(1)$ steps, then $\boldsymbol{\iota}$ also has time complexity $\mathrm{O}(t(n))$.

Due to space limit, the proof of correctness of $\boldsymbol{\iota}$ is deferred to Appendix A.
∎

We are now ready to prove Theorem 4.1.

###### Proof sketch of Theorem 4.1 .

Let $\varphi\in\mathsf{TIME}(t(n))$. Then, there exists a TM $M$ that computes $\varphi$ within $T(n)=\mathrm{O}(t(n))$ steps for every length-$n$ input.

*Case 1:* There exists $n_{0}\in\mathbb{N}$ such that $T(n_{0})<n_{0}$. Thus, the behavior of the TM $M$ depends only on the first $T(n_{0})<n_{0}$ bits of the input. Hence, further increasing the length of the input does not change the behavior of $M$. Therefore, a tighter time complexity $\widetilde{T}(n)$ of $M$ is

$$ $\displaystyle\widetilde{T}(n)\leq T(n_{0})=\mathrm{O}(1),\qquad\forall n\in \mathbb{N}.$ (27) $$

This implies that $\varphi\in\mathsf{TIME}_{2}(1)\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(1)
\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n)\log t(n))$.

*Case 2:* $T(n)\geq n$ for all $n\in\mathbb{N}$. Then by the Hennie–Stearns theorem (Hennie & Stearns, ), $\varphi\in\mathsf{TIME}_{2}(T(n)\log T(n))$. Therefore, by Lemma 4.2,

$$ $\displaystyle\varphi\in\mathsf{TIME}_{2}(t(n)\log t(n))\subseteq\mathsf{TIME}_ {2\textnormal{-PTM}}(t(n)\log t(n)).$ (28) $$

It follows from the above two cases that $\mathsf{TIME}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n)\log t(n))$.
∎

Theorem 4.1 shows that $2$-PTMs have only at most a logarithmic slowdown over TMs. In subsequent Sections 4.2 & 4.3, we will use Theorem 4.1 to characterize the CoT complexity and the precision complexity of our constructed $\varGamma$.

###### Theorem 4.1 (efficient simulation) .

###### Lemma 4.2 (two-tape simulation) .

###### Proof sketch of Lemma 4.2 .

###### Proof sketch of Theorem 4.1 .

### 4.2 CoT complexity

In this subsection, we analyze the CoT complexity of our construction. We will show that our constructed $\varGamma$ can compute any $\mathsf{TIME}_{2}(t(n))$ function within $\mathrm{O}(t(n))$ CoT steps and any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(t(n)\log t(n))$ CoT steps for any length-$n$ input.

###### Definition 4.3 (CoT complexity class) .

Let $\mathsf{CoT}_{\varGamma}(t(n))$ be the class of functions that our constructed Transformer $\varGamma$ can compute within $\mathrm{O}(t(n))$ CoT steps.

###### Lemma 4.4 (CoT complexity for $2$ -PTMs) .

$\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n))$.

###### Proof sketch.

For any $\varphi\in\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))$, since prompt $\boldsymbol{\pi}_{\varphi}$ has length $|\boldsymbol{\pi}_{\varphi}|=\mathrm{O}(1)$, then by Section 3.2, each #, $\tau\texttt{<}$, $\tau\texttt{>}$, $\tau\mathtt{0},$ $\tau\mathtt{1}$ takes $1=\mathrm{O}(1)$ CoT step, and each ${\tau\texttt{!}}_{k}$, ${\tau\texttt{?}}_{k}$ takes at most $\mathrm{O}(|\boldsymbol{\pi}_{\varphi}|)=\mathrm{O}(1)$ CoT steps. This implies that $\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n))$.
∎

###### Corollary 4.5 (CoT complexity for TMs) .

For two-tape TMs, $\mathsf{TIME}_{2}(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n))$. For general TMs, $\mathsf{TIME}(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n)\log t(n))$.

###### Proof.

For two-tape TMs, by Lemmas 4.2 & 4.4,

$$ $\displaystyle\mathsf{TIME}_{2}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM} }(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n)).\qed$ (29) $$

For general TMs, by Theorem 4.1 & Lemma 4.4,

$$ $\mathsf{TIME}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n)\log t(n)) \subseteq\mathsf{CoT}_{\varGamma}(t(n)\log t(n)).$ $$

Corollary 4.5 shows prompting a *single* Transformer can compute any $\mathsf{TIME}_{2}(t(n))$ function within $\mathrm{O}(t(n))$ CoT steps and any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(t(n)\log t(n))$ CoT steps. Notably, this is nearly the same as the CoT complexity of the class of *all* Transformers, which can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(t(n))$ CoT steps. The logarithmic slowdown here is because the class of all Transformers can simulate an unbounded number of tapes while our single Transformer simulates only a finite number of tapes. Assuming $\mathsf{TIME}_{2}(t(n))\neq\mathsf{TIME}(t(n))$, it is unlikely that the CoT complexity $\mathrm{O}(t(n)\log t(n))$ of $\varGamma$ for $\mathsf{TIME}(t(n))$ could be further improved to $\mathrm{O}(t(n))$.

###### Definition 4.3 (CoT complexity class) .

###### Lemma 4.4 (CoT complexity for 2 2 2 2 -PTMs) .

###### Proof sketch.

###### Corollary 4.5 (CoT complexity for TMs) .

###### Proof.

### 4.3 Precision complexity

In this subsection, we analyze the precision complexity of our construction. We will show that our constructed $\varGamma$ can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(\log(n+t(n)))$ bits of precision for any length-$n$ input; in particular, it can decide any $\mathsf{P}$ language within log-precision. Following the common practice in numerical analysis, we assume that each floating-point number has *significant* bits and *guard* bits (Goodman & Feldstein, ), where both significant bits and guard bits are used in arithmetic operations while guard bits are rounded off in number comparisons.

###### Definition 4.6 (Precision complexity class) .

For a complexity function $p(n)$, let $\mathsf{PREC}_{\varGamma}(p(n))$ be the class of functions that our constructed $\varGamma$ can compute using $\mathrm{O}(p(n))$ significant and guard bits.

###### Corollary 4.7 (Precision complexity) .

$\mathsf{TIME}(t(n))\subseteq\mathsf{PREC}_{\varGamma}(\log(n+t(n)))$; $\mathsf{P}\subseteq\mathsf{PREC}_{\varGamma}(\log n)$.

###### Proof sketch.

For any function $\varphi\in\mathsf{CoT}_{\varGamma}(t(n)\log t(n))$, since the prompt $\boldsymbol{\pi}_{\varphi}$ has length $\mathrm{O}(1)$, then by Section 3.3, the total length $I$ of the tokenized input, the prompt, and the CoT steps is

$$ $\displaystyle I=\mathrm{O}(n)+\mathrm{O}(1)+\mathrm{O}(t(n)\log t(n))=\mathrm{ O}(n+t(n)\log t(n)).$ (30) $$

Thus, according to Section 3.4, all the intermediate results during computation are at most $\mathrm{O}(1)$, and attention similarities have mutual differences at least $\Omega\big{(}\frac{1}{I^{5}}\big{)}=\Omega\big{(}\frac{1}{(n+t(n)\log t(n))^{5
}}\big{)}$. This implies

$$ $\displaystyle\mathsf{CoT}_{\varGamma}(t(n)\log t(n))\subseteq\mathsf{PREC}_{ \varGamma}(\log((n+t(n)\log t(n))^{5}))=\mathsf{PREC}_{\varGamma}(\log(n+t(n))).$ (31) $$

It follows from Corollary 4.5 and Equation (31) that

$$ $\displaystyle\mathsf{TIME}(t(n))\subseteq\mathsf{CoT}_{\varGamma}(t(n)\log t(n ))\subseteq\mathsf{PREC}_{\varGamma}(\log(n+t(n))).$ (32) $$

In particular, we have

$$ $\displaystyle\mathsf{P}\subset\mathsf{TIME}(\operatorname{poly}(n))\subseteq \mathsf{PREC}_{\varGamma}(\log(n+\operatorname{poly}(n)))=\mathsf{PREC}_{ \varGamma}(\log n).\qed$ (33) $$

Notably, Corollary 4.7 shows that prompting a *single* Transformer can achieve the same precision complexity as that of the class of *all* Transformers: it is known that the class of all Transformers can compute any $\mathsf{TIME}(t(n))$ function within $\mathrm{O}(\log(n+t(n)))$ precision (Pérez et al., ) while we further show a single Transformer with prompting can as well. This suggests our precision complexity is presumably tight unless there are further advances in the complexity theory of Transformers.

###### Definition 4.6 (Precision complexity class) .

###### Corollary 4.7 (Precision complexity) .

###### Proof sketch.

## 5 Conclusion

In this work, we have shown that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we have shown that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.

Our current work focuses on expressive power rather than learnability. While we have shown the existence of a Transformer on which prompting is Turing-complete, it does not necessarily imply that a Transformer effectively learns to simulate any $2$-PTMs through CoT steps. Investigating the learnability of such a Transformer is an intriguing direction for future research.

## Contents

- A
LABEL:app:pf-ptm::nameA
A.1
LABEL:app:pf-ptm-tm::nameA.1
A.2
LABEL:app:pf-tm-ptm::nameA.2
- B
LABEL:app:pf-main::nameB
B.1
LABEL:app:pf-emb::nameB.1
B.2
LABEL:app:pf-pos::nameB.2
B.3
LABEL:app:pf-after-delim::nameB.3
B.4
LABEL:app:pf-retr-tape::nameB.4
B.5
LABEL:app:pf-prompt::nameB.5
B.6
LABEL:app:pf-prog::nameB.6
B.7
LABEL:app:pf-next-cot::nameB.7
B.8
LABEL:app:pf-readout::nameB.8
B.9
LABEL:app:pf-next-token::nameB.9

## Appendix A Two-tape TMs v.s. 2 2 2 2 -PTMs

In this section, we characterize the relation between two-tape TMs and $2$-PTMs.

### A.1 2 2 2 2 -PTMs simulating two-tape TMs

In this subsection, we show the correctness of the construction presented in Section 4.1.

For each non-halting state $q\in Q\setminus\{q_{\text{halt}}\}$, since we use $1+1+6+6+1+6+6=27$ instructions to simulate its transition rules, we put these instructions at $\boldsymbol{\iota}_{27q:27q+27}$. Thus, the instructions for state $q$ starts at $\iota_{27q}$. Besides that, for the halting state $q_{\text{halt}}=K$, we put the halting instruction after the last non-halting state $K-1$. Thus, the halting instruction is at $\iota_{27(K-1)+27}=\iota_{27K}=\iota_{27q_{\text{halt}}}$. To recapitulate, the instructions for every state $q\in Q$ start at $\iota_{27q}$.

Hence, to make a state transition to $q^{\prime}\in Q$, we should go to instruction $\iota_{27q^{\prime}}$. Since we do not know pointed cell values after we move tape heads, We use two go-to instructions $\langle\mathtt{A}\texttt{!}_{27q^{\prime}},\mathtt{A}\texttt{?}_{27q^{\prime}}\rangle$ with opposite conditions to ensure a state transition to $q^{\prime}$. This establishes the correctness of $\boldsymbol{\eta}_{(q^{\prime},c_{\mathtt{A}},d_{\mathtt{A}},c_{\mathtt{B}},d_
{\mathtt{B}})}$.

To simulate transition rules $\delta(q,\mathtt{0},\mathtt{0}),\delta(q,\mathtt{0},\mathtt{1}),\delta(q,
\mathtt{1},\mathtt{0}),\delta(q,\mathtt{1},\mathtt{1})$ for each non-halting state $q\in Q\setminus\{q_{\text{halt}}\}$, we first use $\mathtt{A}\texttt{?}_{27q+14}$ to check the pointed cell value of tape $\mathtt{A}$ and then use $\mathtt{B}\texttt{?}_{27q+8}$ and $\mathtt{B}\texttt{?}_{27q+21}$ to check the pointed cell value of tape $\mathtt{B}$, where it is easy to see that the indices $27q+14$, $27q+8$, and $27q+21$ are correct.

Finally, note that the simulation is always valid because $2$-PTMs have bi-directional tapes while TMs have uni-directional tapes. This concludes the correctness of the constructed $2$-PTM $\boldsymbol{\iota}$.

It follows that $\mathsf{TIME}_{2}(t(n))\subseteq\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))$.

### A.2 Bi-infinite two-tape TMs simulating 2 2 2 2 -PTMs

In this subsection, we show that any $2$-PTM can be simulated by a TM over two *bi*-infinite tapes.

For any $\varphi\in\mathsf{TIME}_{2\textnormal{-PTM}}(t(n))$, there exists a $2$-PTM $\boldsymbol{\iota}$ that computes $S(\varphi(\boldsymbol{x}))$ from $S(\boldsymbol{x})$ within time $\mathrm{O}(t(n))$. Let $K:=|\boldsymbol{\iota}|$. We will construct a two-tape TM $M=(Q:=\{0,1,\dots,K\},q_{\text{start}}:=0,q_{\text{halt}}:=K,\{\mathtt{0},
\mathtt{1}\},\textvisiblespace:=\mathtt{0},m:=2,\delta:(Q\setminus\{q_{\text{
halt}}\})\times\{\mathtt{0},\mathtt{1}\}^{2}\to Q\times(\{\mathtt{0},\mathtt{1
}\}\times\{\mathtt{L},\mathtt{S},\mathtt{R}\})^{2})$ that simulates the $2$-PTM $\boldsymbol{\iota}$ within time $\mathrm{O}(t(n))$, where we simulate each instruction $\iota_{j}$ ($j=0,\dots,|\boldsymbol{\iota}|-1$) using one state $j$. Let $c_{\mathtt{A}},c_{\mathtt{B}}\in\{\mathtt{0},\mathtt{1}\}$ denote the pointed cell value on tapes $\mathtt{A}$ and $\mathtt{B}$, respectively.

If $\iota_{j}=\texttt{\#}$, then we only make a transition to the halting state $q_{\text{halt}}$:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=(q_{\text{halt}},c_{ \mathtt{A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S}).$ (34) $$

If $\iota_{j}=\mathtt{A}d_{\mathtt{A}}$ ($d_{\mathtt{A}}\in\{\mathtt{L},\mathtt{R}\}$), then we move the head for tape $\mathtt{A}$ and keep the head for tape $\mathtt{B}$:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=(j+1,c_{\mathtt{A}},d_{ \mathtt{A}},c_{\mathtt{B}},\mathtt{S}).$ (35) $$

If $\iota_{j}=\mathtt{B}d_{\mathtt{B}}$ ($d_{\mathtt{B}}\in\{\mathtt{L},\mathtt{R}\}$), then we move the head for tape $\mathtt{B}$ and keep the head for tape $\mathtt{A}$:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=(j+1,c_{\mathtt{A}}, \mathtt{S},c_{\mathtt{B}},d_{\mathtt{B}}).$ (36) $$

If $\iota_{j}=\mathtt{A}c^{\prime}_{\mathtt{A}}$ ($c^{\prime}_{\mathtt{A}}\in\{\mathtt{0},\mathtt{1}\}$), then we write $c^{\prime}_{\mathtt{A}}$ to tape $\mathtt{A}$ and keep tape heads:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=(j+1,c^{\prime}_{\mathtt {A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S}).$ (37) $$

If $\iota_{j}=\mathtt{B}c^{\prime}_{\mathtt{B}}$ ($c^{\prime}_{\mathtt{B}}\in\{\mathtt{0},\mathtt{1}\}$), then we write $c^{\prime}_{\mathtt{B}}$ to tape $\mathtt{B}$ and keep tape heads:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=(j+1,c_{\mathtt{A}}, \mathtt{S},c^{\prime}_{\mathtt{B}},\mathtt{S}).$ (38) $$

If $\iota_{j}=\tau\texttt{!}_{k}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$), we go to $k$ if the pointed cell on tape $\tau$ is $\mathtt{1}$ and to $j+1$ otherwise:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=\begin{cases}(k,c_{ \mathtt{A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S})&\text{if }c_{\tau}=\mathtt{0 },\\ (j+1,c_{\mathtt{A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S})&\text{if }c_{\tau} \neq\mathtt{0}.\end{cases}$ (39) $$

If $\iota_{j}=\tau\texttt{?}_{k}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$), we go to $k$ if the pointed cell on tape $\tau$ is $\mathtt{1}$ and to $j+1$ otherwise:

$$ $\displaystyle\delta(j,c_{\mathtt{A}},c_{\mathtt{B}}):=\begin{cases}(k,c_{ \mathtt{A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S})&\text{if }c_{\tau}=\mathtt{1 },\\ (j+1,c_{\mathtt{A}},\mathtt{S},c_{\mathtt{B}},\mathtt{S})&\text{if }c_{\tau} \neq\mathtt{1}.\end{cases}$ (40) $$

The correctness of the construction above is clear. Since $M$ simulates each $\iota_{j}$ through $1=\mathrm{O}(1)$ transition, then $M$ also has time complexity $\mathrm{O}(t(n))$.

## Appendix B Proof of Theorem 3.1

In this section, we present our detail construction of the Transformer $\varGamma$ as the proof of Theorem 3.1. We will show that we can execute the constructed prompts using affine maps, ReLU activation, layer normalization, and causal attention. Some key ideas are presented in Section 3.4 in the main paper. Unless otherwise specified, the similarity map we use in causal attention is the identity function.

### B.1 Embedding layer

Here, we present our construction of the token embedding and the positional encoding in the embedding layer $\varGamma_{\text{emb}}$. Let $\boldsymbol{v}=v_{0}\cdots v_{|\boldsymbol{v}|-1}\in\varSigma^{+}$ denote the input token sequence of the Transformer. For each token $v_{i}$ ($i=0,\dots,v_{|\boldsymbol{v}|-1}$), we use the one-hot representation as its embedding:

$$ $\displaystyle z^{\text{is }\sigma}_{i}:=1_{[v_{i}=\sigma]},\qquad\sigma\in\varSigma.$ (41) $$

As described in Section 3.4, we use the following positional encoding for each position $i$:

$$ $\displaystyle p_{i}$ $\displaystyle:=1-\frac{(i+1)(i+2)+1}{\sqrt{(i+1)^{2}+1}\sqrt{(i+2)^{2}+1}}.$ (42) $$

### B.2 Other positional identifiers

In addition to the positional encoding, we compute three other positional identifiers to be used later. First, we use causal attention with query $1$, key $1$, and value $z^{\text{is }\texttt{\textasciicircum}}_{j}$ to compute

$$ $\displaystyle z^{\text{pos, 1}}_{i}:=\frac{1}{i+1}\sum_{j=0}^{i}z^{\text{is } \texttt{\textasciicircum}}_{j}=\frac{1}{i+1}.$ (43) $$

Next, we use layer normalization ($\operatorname{LN}$) to compute two other positional identifiers:

$$ $\displaystyle(z^{\text{pos, 2}}_{i},z^{\text{pos, 3}}_{i}):=\operatorname{LN}( 1,z^{\text{pos, 1}}_{i})=\bigg{(}\frac{i+1}{\sqrt{(i+1)^{2}+1}},\frac{1}{\sqrt {(i+1)^{2}+1}}\bigg{)}.$ (44) $$

### B.3 Parsing CoT steps

Since the prompt and the CoT share some tokens, we need distinguish CoT steps from the prompt according to the position of the delimiter token $. Specifically, we need an indicator of whether each token $v_{i}$ is located after the delimiter token $ or not. Thus, we use causal attention with query $1$, key $1$, and value $z^{\text{is }\texttt{\textdollar}}$ to compute the discounted indicator:

$$ $\displaystyle z^{\text{after delim, disc}}_{i}:=\frac{1}{i+1}\sum_{j=0}^{i}z^{ \text{is }\texttt{\textdollar}}_{j}=\frac{1_{[\exists j\leq i:v_{j}=\texttt{ \textdollar}]}}{i+1}.$ (45) $$

Then, we use layer normalization to convert it to a Boolean value:

$$ $\displaystyle z^{\text{after delim}}_{i}:=\operatorname{LN}(z^{\text{after delim, disc}}_{i})=1_{[\exists j\leq i:v_{j}=\texttt{\textdollar}]}.$ (46) $$

Next, we check if a token is a CoT step of writing a cell using $\operatorname{ReLU}$-implemented Boolean algebra:

$$ $\displaystyle z^{\text{is }\tau\text{ write}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{is }\tau\mathtt{0}}_{i}+z^{\text{ is }\tau\mathtt{1}}_{i}+z^{\text{after delim}}_{i}-1),\quad\tau\in\{\mathtt{A} ,\mathtt{B}\};$ (47) $$

we can compute the value that is being written using $\operatorname{ReLU}$:

$$ $\displaystyle z^{\tau\text{ write}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{is }\tau\mathtt{1}}_{i}+z^{\text{ after delim}}_{i}-1),\qquad\tau\in\{\mathtt{A},\mathtt{B}\};$ (48) $$

we can also compute the direction of head move in a CoT step using $\operatorname{ReLU}$:

$$ $\displaystyle z^{\tau\text{ move}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{is }\tau\mathtt{R}}_{i}+z^{\text{ after delim}}_{i}-1)-\operatorname{ReLU}(z^{\text{is }\tau\mathtt{L}}_{i}+z^{ \text{after delim}}_{i}-1),\quad\tau\in\{\mathtt{A},\mathtt{B}\}.$ (49) $$

### B.4 Retrieving pointed tape cells

Before retrieving the pointed tape cells, we need to compute the current positions of tape heads. Since attention cannot compute sums directly, we use the idea presented in Section 3.4 to compute a normalized representation of the position. Specifically, we first use causal attention with query $1$, key $1$, and value $z^{\tau\text{ move}}_{j}$ to compute discounted head positions:

$$ $\displaystyle z^{\tau\text{ cur disc}}_{i}$ $\displaystyle:=\frac{1}{i+1}\sum_{j=0}^{i}z^{\tau\text{ move}}_{j},\qquad\tau \in\{\mathtt{A},\mathtt{B}\}.$ (50) $$

Then, we use $z^{\text{pos, 1}}_{i}=\frac{1}{i+1}$ and $\operatorname{LN}$ to compute a normalized representation of head positions:

$$ $\displaystyle(z^{\tau\text{ cur norm}}_{i},z^{\tau\text{ cur one norm}}_{i}):= {}\operatorname{LN}(z^{\tau\text{ cur disc}}_{i},z^{\text{pos, 1}}_{i})$ (51) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{\sum_{j=0}^{i}z^{\tau\text{ move}}_{j}}{\sqrt{(\sum _{j=0}^{i}z^{\tau\text{ move}}_{j})^{2}+1}},\frac{1}{\sqrt{(\sum_{j=0}^{i}z^{ \tau\text{ move}}_{j})^{2}+1}}\bigg{)},\quad\tau\in\{\mathtt{A},\mathtt{B}\}.$ (52) $$

Next, we can retrieve the pointed tape cells by finding the last write step at the same position. We use causal attention with query $(1,z^{\tau\text{ cur norm}}_{i},z^{\tau\text{ cur one norm}}_{i},p_{i})^{
\mathsf{T}}$, key $(z^{\text{is }\tau\text{ write}}_{j},z^{\tau\text{ cur norm}}_{j},z^{\tau\text
{ cur one norm}}_{j},-z^{\text{pos, 1}}_{j})^{\mathsf{T}}$, and value $(z^{\tau\text{ write}}_{j},z^{\tau\text{ cur norm}}_{j},z^{\text{is }\tau\text
{ write}}_{j})^{\mathsf{T}}$ to compute the retrieved tape cells $(z^{\tau\text{ retr}}_{i},z^{\tau\text{ retr cur norm}}_{i},z^{\tau\text{ retr
is write}}_{i})^{\mathsf{T}}$ ($\tau\in\{\mathtt{A},\mathtt{B}\}$).
Note that we also compute $z^{\tau\text{ retr cur norm}}_{i}$ and $z^{\tau\text{ retr is write}}_{i}$ here because there is a caveat: the pointed tape cells might not have been written yet. We use $\operatorname{LN}$ and $\operatorname{ReLU}$ to compute an indicator of whether the pointed tape cells have not been written:

$$ $\displaystyle z^{\tau\text{ not found}}_{i}:={}$ $\displaystyle\operatorname{ReLU}(\operatorname{LN}(z^{\tau\text{ cur norm}}_{i }-z^{\tau\text{ retr cur norm}}_{i}))+\operatorname{ReLU}(\operatorname{LN}(z^ {\tau\text{ retr cur norm}}_{i}-z^{\tau\text{ cur norm}}_{i}))$ $\displaystyle={}$ $\displaystyle 1_{[z^{\tau\text{ cur norm}}_{i}\neq z^{\tau\text{ retr cur norm }}_{i}]},\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\tau\in\{ \mathtt{A},\mathtt{B}\}.$ (53) $$

If a retreived tape cell has not been written yet, it must have a blank value $\mathtt{0}$:

$$ $\displaystyle z^{\tau\text{ val}}_{i}:=\operatorname{ReLU}(z^{\tau\text{ retr} }_{i}-z^{\tau\text{ not found}}_{i}+z^{\tau\text{ retr is write}}_{i}-1),\quad \tau\in\{\mathtt{A},\mathtt{B}\}.$ (54) $$

### B.5 Parsing instructions in prompt

Recall that each instruction is encoded into one or more tokens. Thus, we first compute whether each token is the start of a instruction in the prompt:

$$ $\displaystyle z^{\text{is inst}}_{i}:=\operatorname{ReLU}(z^{\text{is }\texttt {\#}}_{i}$ $\displaystyle+z^{\text{is }\mathtt{AL}}_{i}+z^{\text{is }\mathtt{BL}}_{i}+z^{ \text{is }\mathtt{AR}}_{i}+z^{\text{is }\mathtt{BR}}_{i}$ (55) $\displaystyle+z^{\text{is }\mathtt{A0}}_{i}+z^{\text{is }\mathtt{B0}}_{i}+z^{ \text{is }\mathtt{A1}}_{i}+z^{\text{is }\mathtt{B1}}_{i}$ (56) $\displaystyle+z^{\text{is }\mathtt{A}\texttt{!}}_{i}+z^{\text{is }\mathtt{B} \texttt{!}}_{i}+z^{\text{is }\mathtt{A}\texttt{?}}_{i}+z^{\text{is }\mathtt{B} \texttt{?}}_{i}-z^{\text{after delim}}_{i}).$ (57) $$

We compute a *program index* $t$ for the start token of each instruction. We use causal attention with query $1$, key $1$, and value $z^{\text{is inst}}_{j}$ to compute the program index of each token in the prompt:

$$ $\displaystyle z^{\text{prog idx disc, raw}}_{i}:=\frac{1}{i+1}\sum_{j=0}^{i}z^ {\text{is inst}}_{j}.$ (58) $$

We further subtract $1$ from $\sum_{j=0}^{i}z^{\text{is inst}}_{j}$ to handle the lag between the prompt and the CoT:

$$ $\displaystyle z^{\text{prog idx disc}}_{i}:=z^{\text{prog idx disc, raw}}_{i}- z^{\text{pos, 1}}=\frac{1}{i+1}\sum_{j=0}^{i}z^{\text{is inst}}_{j}-\frac{1}{i +1}.$ (59) $$

Then, we use $\operatorname{LN}$ to compute a normalized representation of $\sum_{j=0}^{i}z^{\text{is inst}}_{j}-1$:

$$ $\displaystyle(z^{\text{prog idx norm}}_{i},z^{\text{prog idx one norm}}_{i}):= \operatorname{LN}(z^{\text{prog idx disc}}_{i},z^{\text{pos, 1}}_{i})$ (60) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{\sum_{j=0}^{i}z^{\text{is inst}}_{j}-1}{\sqrt{(\sum _{j=0}^{i}z^{\text{is inst}}_{j}-1)^{2}+1}},\frac{1}{\sqrt{(\sum_{j=0}^{i}z^{ \text{is inst}}_{j}-1)^{2}+1}}\bigg{)}.$ (61) $$

Besides that, since go-to’s are special instructions that need multiple tokens to encode, we also check whether a token is the start of a go-to instruction:

$$ $\displaystyle z^{\text{is goto cond}}_{i}:=z^{\text{is }\mathtt{A}\texttt{!}}_ {i}+z^{\text{is }\mathtt{B}\texttt{!}}_{i}+z^{\text{is }\mathtt{A}\texttt{?}}_ {i}+z^{\text{is }\mathtt{B}\texttt{?}}_{i}.$ (62) $$

We also need a *go-to index* for tokens $\texttt{-},\texttt{+},\texttt{@}$ in the prompt to mark the order of tokens within each go-to instruction. To compute it, we first compute the reciprocal number of tokens between $v_{i}$ and the start token $v_{i^{\prime}}$ of the current go-to instruction, using causal attention with query $1$, key $z^{\text{prog idx norm}}_{j}$, and value $z^{\text{is goto cond}}_{j}$:

$$ $\displaystyle z^{\text{goto one disc}}_{i}:=\frac{\sum_{j=i^{\prime}}^{i}z^{ \text{is goto cond}}_{j}}{\sum_{j=i^{\prime}}^{i}1}=\frac{1}{i-i^{\prime}+1}.$ (63) $$

Then, we use $\operatorname{LN}$ to compute a normalized representation of the go-to index:

$$ $\displaystyle(z^{\text{goto idx norm, raw}}_{i},z^{\text{goto one norm, raw}}_ {i}):={}$ $\displaystyle\operatorname{LN}(1-z^{\text{goto one disc}}_{i},z^{\text{goto one disc}}_{i})$ (64) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{i-i^{\prime}+1}{\sqrt{(i-i^{\prime}+1)^{2}+1}}, \frac{1}{\sqrt{(i-i^{\prime}+1)^{2}+1}}\bigg{)}.$ (65) $$

To match the go-to index of non-go-to tokens, we finally adjust them if $v_{i}$ is the start token $v_{i}^{\prime}$ of the current go-to instruction:

$$ $\displaystyle z^{\text{goto idx norm}}_{i}$ $\displaystyle:=z^{\text{goto idx norm, raw}}_{i}+z^{\text{is goto cond}}_{i},$ (66) $\displaystyle z^{\text{goto one norm}}_{i}$ $\displaystyle:=z^{\text{goto one norm, raw}}_{i}-z^{\text{is goto cond}}_{i}.$ (67) $$

That is, when $v_{i}$ is the start token $v_{i}^{\prime}$ of a go-to instruction, we instead have

$$ $\displaystyle(z^{\text{goto idx norm}}_{i},z^{\text{goto one norm}}_{i})=(1,0).$ (68) $$

### B.6 Locating current CoT step

Here, we describe how to locate the current instruction to execute. We can imagine a program pointer $t$ that indicates the instruction $\iota_{t}$ we are currently executing. A caveat here is that each go-to instruction needs multiple CoT steps. Thus, it is important to check whether it is during a go-to instruction or not.

First, we compute how each go-to step contributes to the program pointer via $\operatorname{ReLU}$:

$$ $\displaystyle z^{\text{prog move}}_{i}:=\operatorname{ReLU}(z^{\text{is } \texttt{+}}_{i}+z^{\text{after delim}}_{i}-1)-\operatorname{ReLU}(z^{\text{is }\texttt{-}}_{i}+z^{\text{after delim}}_{i}-1).$ (69) $$

Then, we use causal attention with query $1$, key $1$, and value $z^{\text{prog move}}_{i}$ to compute the discounted total contribution:

$$ $\displaystyle z^{\text{prog move disc}}_{i}:=\frac{1}{i+1}\sum_{j=0}^{i}z^{ \text{prog move}}_{j};$ (70) $$

and use $\operatorname{LN}$ to compute a normalized representation of $\sum_{j=0}^{i}z^{\text{prog move}}_{j}$:

$$ $\displaystyle(z^{\text{prog move norm}}_{i},z^{\text{prog move one norm}}_{i}) :=\operatorname{LN}(z^{\text{prog move disc}}_{i},z^{\text{pos, 1}}_{i})$ (71) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{\sum_{j=0}^{i}z^{\text{prog move}}_{j}}{\sqrt{(\sum _{j=0}^{i}z^{\text{prog move}}_{j})^{2}+1}},\frac{1}{\sqrt{(\sum_{j=0}^{i}z^{ \text{prog move}}_{j})^{2}+1}}\bigg{)}.$ (72) $$

Next, we check whether the token $v_{i}$ is the start token $v_{i}^{\prime}$ of the current execution step record in the CoT:

$$ $\displaystyle z^{\text{is rec start}}_{i}:=z^{\text{is }\texttt{ \textasciicircum}}_{i}+\operatorname{ReLU}($ $\displaystyle z^{\text{is }\mathtt{AL}}_{i}+z^{\text{is }\mathtt{BL}}_{i}+z^{ \text{is }\mathtt{AR}}_{i}+z^{\text{is }\mathtt{BR}}_{i}$ (73) $\displaystyle+{}$ $\displaystyle z^{\text{is }\mathtt{A0}}_{i}+z^{\text{is }\mathtt{B0}}_{i}+z^{ \text{is }\mathtt{A1}}_{i}+z^{\text{is }\mathtt{B1}}_{i}$ (74) $\displaystyle+{}$ $\displaystyle z^{\text{is }\texttt{/}}_{i}+z^{\text{is }\texttt{=}}_{i}+z^{ \text{after delim}}_{i}-1),$ (75) $$

where we also add $z^{\text{is }\texttt{\textasciicircum}}_{i}$ here for convenience later. Similarly, we check whether the token $v_{i}$ is the ending token $v_{i}^{\prime}$ of the current execution step record in the CoT:

$$ $\displaystyle z^{\text{is rec end}}_{i}:=\operatorname{ReLU}(z^{\text{is } \texttt{\textdollar}}_{i}+$ $\displaystyle z^{\text{is }\mathtt{AL}}_{i}+z^{\text{is }\mathtt{BL}}_{i}+z^{ \text{is }\mathtt{AR}}_{i}+z^{\text{is }\mathtt{BR}}_{i}$ (76) $\displaystyle+{}$ $\displaystyle z^{\text{is }\mathtt{A0}}_{i}+z^{\text{is }\mathtt{B0}}_{i}+z^{ \text{is }\mathtt{A1}}_{i}+z^{\text{is }\mathtt{B1}}_{i}$ (77) $\displaystyle+{}$ $\displaystyle z^{\text{is }\texttt{@}}_{i}+z^{\text{after delim}}_{i}-1).$ (78) $$

Then, imagine that each token has a *record index* to mark which each execution step it belongs to. To compute it, we first compute the reciprocal number of execution steps $t^{\prime}$ so far, using causal attention with query $1$, key $z^{\text{is rec start}}_{j}$, and value $z^{\text{is }\texttt{\textasciicircum}}_{j}$:

$$ $\displaystyle z^{\text{prog rec one disc}}_{i}:=\frac{\sum_{j=0}^{i}z^{\text{ is rec start}}_{j}z^{\text{is }\texttt{\textasciicircum}}_{j}}{\sum_{j=0}^{i}z ^{\text{is rec start}}_{j}}=\frac{1}{t^{\prime}+1}.$ (79) $$

We then compute a normalized representation of $t^{\prime}+1$ using $\operatorname{LN}$:

$$ $\displaystyle(z^{\text{prog rec norm}}_{i},z^{\text{prog rec one norm}}_{i}):={}$ $\displaystyle\operatorname{LN}(1,z^{\text{prog rec one disc}}_{i})$ (80) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{t^{\prime}+1}{\sqrt{(t^{\prime}+1)^{2}+1}},\frac{1} {\sqrt{(t^{\prime}+1)^{2}+1}}\bigg{)}.$ (81) $$

Next, since each go-to execution step needs multiple CoT steps, we need to handle go-to execution step records specially when the go-to condition is satisfied. We can image that each CoT step has a *temporary program index* that marks the order of each token in a go-to execution step record. To compute it, we first compute the reciprocal number of tokens between $v_{i}$ and the start token $v_{i^{\prime}}$ of the current go-to execution step record, using causal attention with query $1$, key $-z^{\text{prog rec one disc}}_{j}$, and value $z^{\text{is }\texttt{=}}_{j}$:

$$ $\displaystyle z^{\text{prog tmp one disc}}_{i}:=\frac{\sum_{j=i^{\prime}}^{i}z ^{\text{is }\texttt{=}}_{j}}{\sum_{j=i^{\prime}}^{i}1}=\frac{1}{i-i^{\prime}+1}.$ (82) $$

With this, we can compute a normalized representation of $i-i^{\prime}+1$ using $\operatorname{LN}$:

$$ $\displaystyle(z^{\text{prog tmp norm, raw}}_{i},z^{\text{prog tmp one norm, raw}}_{i}):={}$ $\displaystyle\operatorname{LN}(1,z^{\text{prog tmp one disc}}_{i})$ (83) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{i-i^{\prime}+1}{\sqrt{(i-i^{\prime}+1)^{2}+1}}, \frac{1}{\sqrt{(i-i^{\prime}+1)^{2}+1}}\bigg{)}.$ (84) $$

To match the temporary program index of non-go-to execution steps, we further adjust them if $v_{i}$ is the ending token of the current go-to instruction:

$$ $\displaystyle z^{\text{prog tmp norm}}_{i}:=\operatorname{ReLU}(z^{\text{prog tmp norm, raw}}_{i}-z^{\text{is rec end}}_{i})+z^{\text{is rec end}}_{i},$ (85) $\displaystyle z^{\text{prog tmp one norm}}_{i}:=\operatorname{ReLU}(z^{\text{ prog tmp one norm, raw}}_{i}-z^{\text{is rec end}}_{i}).$ (86) $$

That is, when $v_{i}$ is the ending token of the current go-to instruction, we instead have

$$ $\displaystyle(z^{\text{prog tmp norm}}_{i},z^{\text{prog tmp one norm}}_{i})=( 1,0).$ (87) $$

We will use the quantities above to identify the instruction to execute.

### B.7 Executing next CoT step

To generate the next token, we need to execute the current instruction and record it via a CoT step. Before that, we check whether $v_{i}$ belongs to a satisfied go-to execution step record:

$$ $\displaystyle z^{\text{is rec goto}}_{i}:=\operatorname{ReLU}(z^{\text{is } \texttt{=}}_{i}+z^{\text{is }\texttt{-}}_{i}+z^{\text{is }\texttt{+}}_{i}+z^{ \text{after delim}}_{i}-1).$ (88) $$

Another quantity we will need is how each CoT step contributes to the current program pointer:

$$ $\displaystyle z^{\text{prog cur move}}_{i}:=\operatorname{ReLU}($ $\displaystyle z^{\text{is }\mathtt{AL}}_{i}+z^{\text{is }\mathtt{BL}}_{i}+z^{ \text{is }\mathtt{AR}}_{i}+z^{\text{is }\mathtt{BR}}_{i}$ (89) $\displaystyle+{}$ $\displaystyle z^{\text{is }\mathtt{A0}}_{i}+z^{\text{is }\mathtt{B0}}_{i}+z^{ \text{is }\mathtt{A1}}_{i}+z^{\text{is }\mathtt{B1}}_{i}$ (90) $\displaystyle+{}$ $\displaystyle z^{\text{is }\texttt{/}}_{i}+z^{\text{is }\texttt{+}}_{i}+z^{ \text{after delim}}_{i}-1)-\operatorname{ReLU}(z^{\text{is }\texttt{-}}_{i}+z^ {\text{after delim}}_{i}-1).$ (91) $$

We also compute an auxiliary bound $z^{\text{prog rec diff}}_{i}$ on the differences between some attention scores using causal attention with query $(z^{\text{prog rec norm}}_{i},z^{\text{prog rec one norm}}_{i})^{\mathsf{T}}$, key $(z^{\text{pos, 2}}_{j},z^{\text{pos, 3}}_{j})^{\mathsf{T}}$, and value $p_{j}$. We further compute an auxiliary quantity:

$$ $\displaystyle z^{\text{prog rec bias}}_{i}:=3-\frac{1}{2}\operatorname{ReLU}(z ^{\text{prog rec diff}}_{i}+2z^{\text{is rec goto}}_{i}-2).$ (92) $$

It is easy to see that $z^{\text{prog rec diff}}_{i}<3$ if and only if $z^{\text{is rec goto}}_{i}=1$. Using this quantity, we will be able to avoid attending to tokens outside the current execution step record. Next, we use it to identify the next instruction to execute. We first compute the discounted program index of the instruction that we need to execute, which is proportional to the sum of $z^{\text{prog cur move}}_{j}$ until the beginning token $v_{i^{\prime}}$ of the current execution step record, using causal attention with query $(z^{\text{prog rec bias}}_{i},-z^{\text{prog rec norm}}_{i},-z^{\text{prog rec
one norm}}_{i})^{\mathsf{T}}$, key $(1,z^{\text{prog rec norm}}_{j},z^{\text{prog rec one norm}}_{j})^{\mathsf{T}}$, value $(z^{\text{prog cur move}}_{j},z^{\text{is }\texttt{\textasciicircum}}_{j})^{
\mathsf{T}}$, and similarity function $\operatorname{sim}(x):=2-\operatorname{ReLU}(2-x)=\min\{x,2\}$:

$$ $\displaystyle z^{\text{prog cur disc}}_{i}:=\frac{\sum_{j=0}^{i^{\prime}}z^{ \text{prog cur move}}_{j}}{\sum_{j=0}^{i^{\prime}}1}=\frac{\sum_{j=0}^{i^{ \prime}}z^{\text{prog cur move}}_{j}}{i^{\prime}+1},$ (93) $\displaystyle z^{\text{prog cur one disc}}_{i}:=\frac{\sum_{j=0}^{i^{\prime}}z ^{\text{is }\texttt{\textasciicircum}}_{j}}{\sum_{j=0}^{i^{\prime}}1}=\frac{1} {i^{\prime}+1}.$ (94) $$

Then, we use $\operatorname{LN}$ to compute a normalized representation of $\sum_{j=0}^{i^{\prime}}z^{\text{prog cur move}}_{j}$:

$$ $\displaystyle(z^{\text{prog cur norm}}_{i},z^{\text{prog cur one norm}}_{i}):= \operatorname{LN}(z^{\text{prog cur disc}}_{i},z^{\text{prog cur one disc}}_{i})$ (95) $\displaystyle={}$ $\displaystyle\bigg{(}\frac{\sum_{j=0}^{i}z^{\text{prog cur move}}_{j}}{\sqrt{( \sum_{j=0}^{i}z^{\text{prog cur move}}_{j})^{2}+1}},\frac{1}{\sqrt{(\sum_{j=0} ^{i}z^{\text{prog cur move}}_{j})^{2}+1}}\bigg{)}.$ (96) $$

Next, we find the instruction $\iota_{t}$ whose program index matches the current program pointer and whose go-to index matches the current temporary program index, using causal attention with query $(z^{\text{prog cur norm}}_{i},z^{\text{prog cur one norm}}_{i},z^{\text{prog
tmp norm}}_{i},z^{\text{prog tmp one norm}}_{i},p_{i},-1)^{\mathsf{T}}$, key $(z^{\text{prog idx norm}}_{j},z^{\text{prog idx one norm}}_{j},z^{\text{goto
idx norm}}_{j},z^{\text{goto one norm}}_{j},z^{\text{pos, 1}}_{j},1)^{\mathsf{
T}}$, and value $z^{\text{is }\sigma}_{j}$:

$$ $\displaystyle z^{\text{token is }\sigma}_{i}$ $\displaystyle:=z^{\text{is }\sigma}_{t},\quad\sigma\in\{\texttt{\#},\mathtt{A} \mathtt{L},\mathtt{B}\mathtt{L},\mathtt{A}\mathtt{R},\mathtt{B}\mathtt{R}, \mathtt{A}\mathtt{0},\mathtt{B}\mathtt{0},\mathtt{A}\mathtt{1},\mathtt{B} \mathtt{1},\mathtt{A}\texttt{!},\mathtt{B}\texttt{!},\mathtt{A}\texttt{?}, \mathtt{B}\texttt{?},\texttt{-},\texttt{+},\texttt{@}\};$ (97) $\displaystyle z^{\text{token is }\texttt{:}}_{i}$ $\displaystyle:=z^{\text{is }\texttt{\#}}_{t}.$ (98) $$

Note that exactly one of them is $1$. It remains to execute the instruction $\iota_{t}$ and record its outcome.
If $z^{\text{token is }\sigma}_{i}=1$ for some $\sigma\in\{\mathtt{A}\texttt{!},\mathtt{B}\texttt{!},\mathtt{A}\texttt{?},
\mathtt{B}\texttt{?}\}$, then we need to check whether the go-to condition is satisfied or not:

$$ $\displaystyle z^{\text{sat }\mathtt{A}\texttt{!}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{token is }\mathtt{A}\texttt{!}}_{i }-z^{\mathtt{A}\text{ val}}_{i}),$ (99) $\displaystyle z^{\text{sat }\mathtt{B}\texttt{!}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{token is }\mathtt{B}\texttt{!}}_{i }-z^{\mathtt{B}\text{ val}}_{i}),$ (100) $\displaystyle z^{\text{sat }\mathtt{A}\texttt{?}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{token is }\mathtt{A}\texttt{?}}_{i }+z^{\mathtt{A}\text{ val}}_{i}-1),$ (101) $\displaystyle z^{\text{sat }\mathtt{B}\texttt{?}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{token is }\mathtt{B}\texttt{?}}_{i }+z^{\mathtt{B}\text{ val}}_{i}-1).$ (102) $$

They enable us to choose = (satisfied) or / (unsatisfied):

$$ $\displaystyle z^{\text{token is }\texttt{=}}_{i}$ $\displaystyle:=z^{\text{sat }\mathtt{A}\texttt{!}}_{i}+z^{\text{sat }\mathtt{B }\texttt{!}}_{i}+z^{\text{sat }\mathtt{A}\texttt{?}}_{i}+z^{\text{sat }\mathtt {B}\texttt{?}}_{i},$ (103) $\displaystyle z^{\text{token is }\texttt{/}}_{i}$ $\displaystyle:=z^{\text{token is }\mathtt{A}\texttt{!}}_{i}+z^{\text{token is }\mathtt{B}\texttt{!}}_{i}+z^{\text{token is }\mathtt{A}\texttt{?}}_{i}+z^{ \text{token is }\mathtt{B}\texttt{?}}_{i}-z^{\text{token is }\texttt{=}}_{i}.$ (104) $$

### B.8 Extracting final output

After execution, the content left on the tape $\mathtt{A}$ is the Shannon-encoded output $S(\varphi(\boldsymbol{x}))$. We need to extract the decoded output $\varphi(\boldsymbol{x})$ from the previous CoT steps.

First, we need to check whether we have arrived at the final output stage:

$$ $\displaystyle z^{\text{is read key}}_{i}:=z^{\text{is }\texttt{:}}_{i}+z^{ \text{is }\mathtt{0}}_{i}+z^{\text{is }\mathtt{1}}_{i}.$ (105) $$

Suppose that we are now trying to find the $k$-th token of the output $\varphi(\boldsymbol{x})$. Recall that the $k$-th token ($k\geq 0$) of the output $\varphi(\boldsymbol{x})$ corresponds to the $(2k)$-th and $(2k+1)$-th tokens of $S(\varphi(\boldsymbol{x}))$. To help compute the indices $2k$ and $2k+1$, we compute the following shifts:

$$ $\displaystyle z^{\text{read cur0 shift}}_{i}$ $\displaystyle:=2(z^{\text{is }\mathtt{0}}_{i}+z^{\text{is }\mathtt{1}}_{i}),$ (106) $\displaystyle z^{\text{read cur1 shift}}_{i}$ $\displaystyle:=z^{\text{is }\texttt{:}}_{i}+2(z^{\text{is }\mathtt{0}}_{i}+z^{ \text{is }\mathtt{1}}_{i}).$ (107) $$

Suppose that token : is the $t$-th token in the generated CoT. We use causal attention with query $1$, key $z^{\text{is read key}}_{j}$, and value $(z^{\text{read cur0 shift}}_{j},z^{\text{read cur1 shift}}_{j},z^{\text{is }
\texttt{:}}_{j})^{\mathsf{T}}$ to compute the discounted $2k$ and $2k+1$ for $i=t+k$:

$$ $\displaystyle z^{\text{read cur0 disc}}_{i}$ $\displaystyle:=\frac{1}{\sum_{j=0}^{i}z^{\text{is read key}}_{j}}\sum_{j=0}^{i }z^{\text{read cur0 shift}}_{j}=\frac{2k}{i-t+1},$ (108) $\displaystyle z^{\text{read cur1 disc}}_{i}$ $\displaystyle:=\frac{1}{\sum_{j=0}^{i}z^{\text{is read key}}_{j}}\sum_{j=0}^{i }z^{\text{read cur1 shift}}_{j}=\frac{2k+1}{i-t+1},$ (109) $\displaystyle z^{\text{read one disc}}_{i}$ $\displaystyle:=\frac{1}{\sum_{j=0}^{i}z^{\text{is read key}}_{j}}\sum_{j=0}^{i }z^{\text{is }\texttt{:}}_{j}=\frac{1}{i-t+1}.$ (110) $$

We use layer normalization to compute representations of $2k$ and $2k+1$:

$$ $\displaystyle(z^{\text{read cur0 norm}}_{i},z^{\text{read cur0 one norm}}_{i}) :={}$ $\displaystyle\operatorname{LN}(z^{\text{read cur0 disc}}_{i},z^{\text{read one disc}}_{i})$ $\displaystyle={}$ $\displaystyle\bigg{(}\frac{2k}{\sqrt{(2k)^{2}+1}},\frac{1}{\sqrt{(2k)^{2}+1}} \bigg{)},$ (111) $\displaystyle(z^{\text{read cur1 norm}}_{i},z^{\text{read cur1 one norm}}_{i}) :={}$ $\displaystyle\operatorname{LN}(z^{\text{read cur1 disc}}_{i},z^{\text{read one disc}}_{i})$ $\displaystyle={}$ $\displaystyle\bigg{(}\frac{2k+1}{\sqrt{(2k+1)^{2}+1}},\frac{1}{\sqrt{(2k+1)^{2 }+1}}\bigg{)}.$ (112) $$

Next, similarly with Appendix B.4, we retrieve the $(2k)$-th and $(2k+1)$-th tokens of $S(\varphi(\boldsymbol{x}))$ as follows. We use causal attention with query $(1,z^{\text{read cur0 norm}}_{i},z^{\text{read cur0 one norm}}_{i},p_{i})^{
\mathsf{T}}$, key $(z^{\text{is }\mathtt{A}\text{ write}}_{j},z^{\mathtt{A}\text{ cur norm}}_{j},
z^{\mathtt{A}\text{ cur one norm}}_{j},-z^{\text{pos, 1}}_{j})^{\mathsf{T}}$, and value $(z^{\mathtt{A}\text{ write}}_{j},z^{\mathtt{A}\text{ cur norm}}_{j},z^{\text{
is }\mathtt{A}\text{ write}}_{j})^{\mathsf{T}}$ to compute the retrieved tape cell status $(z^{\text{read retr0}}_{i},z^{\text{read retr0 cur norm}}_{i},z^{\text{read
retr0 is write}}_{i})^{\mathsf{T}}$. We use causal attention with query $(1,z^{\text{read cur1 norm}}_{i},z^{\text{read cur1 one norm}}_{i},p_{i})^{
\mathsf{T}}$, key $(z^{\text{is }\mathtt{A}\text{ write}}_{j},z^{\mathtt{A}\text{ cur norm}}_{j},
z^{\mathtt{A}\text{ cur one norm}}_{j},-z^{\text{pos, 1}}_{j})^{\mathsf{T}}$, and value $(z^{\mathtt{A}\text{ write}}_{j},z^{\mathtt{A}\text{ cur norm}}_{j},z^{\text{
is }\mathtt{A}\text{ write}}_{j})^{\mathsf{T}}$ to compute the retrieved tape cell status $(z^{\text{read retr1}}_{i},z^{\text{read retr1 cur norm}}_{i},z^{\text{read
retr1 is write}}_{i})^{\mathsf{T}}$. We use $\operatorname{LN}$ and $\operatorname{ReLU}$ to compute an indicator of whether the retrieved tape cells have not been written:

$$ $\displaystyle z^{\text{read retr0 not found}}_{i}:={}$ $\displaystyle\operatorname{ReLU}(\operatorname{LN}(z^{\text{read cur0 norm}}_{ i}-z^{\text{read retr0 cur norm}}_{i}))+\operatorname{ReLU}(\operatorname{LN}( z^{\text{read retr0 cur norm}}_{i}-z^{\text{read cur0 norm}}_{i}))$ $\displaystyle={}$ $\displaystyle 1_{[z^{\text{read cur0 norm}}_{i}\neq z^{\text{read retr0 cur norm}}_{i}]},$ (113) $\displaystyle z^{\text{read retr1 not found}}_{i}:={}$ $\displaystyle\operatorname{ReLU}(\operatorname{LN}(z^{\text{read cur1 norm}}_{ i}-z^{\text{read retr1 cur norm}}_{i}))+\operatorname{ReLU}(\operatorname{LN}( z^{\text{read retr1 cur norm}}_{i}-z^{\text{read cur1 norm}}_{i}))$ $\displaystyle={}$ $\displaystyle 1_{[z^{\text{read cur1 norm}}_{i}\neq z^{\text{read retr1 cur norm}}_{i}]}.$ (114) $$

Finally, we can obtain the values of cells $2k$ and $2k+1$:

$$ $\displaystyle z^{\text{read retr0 val}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{read retr0}}_{i}-z^{\text{read retr0 not found}}_{i}+z^{\text{read retr0 is write}}_{i}-1),$ (115) $\displaystyle z^{\text{read retr1 val}}_{i}$ $\displaystyle:=\operatorname{ReLU}(z^{\text{read retr1}}_{i}-z^{\text{read retr1 not found}}_{i}+z^{\text{read retr1 is write}}_{i}-1).$ (116) $$

Using the quantities above, we can decide the next token to generate:

$$ $\displaystyle z^{\text{token is }\mathtt{0}}_{i}$ $\displaystyle:=2\operatorname{ReLU}(z^{\text{is read key}}_{i}+z^{\text{read retr0 val}}_{i}-z^{\text{read retr1 val}}_{i}-1),$ (117) $\displaystyle z^{\text{token is }\mathtt{1}}_{i}$ $\displaystyle:=2\operatorname{ReLU}(z^{\text{is read key}}_{i}+z^{\text{read retr0 val}}_{i}+z^{\text{read retr1 val}}_{i}-2),$ (118) $\displaystyle z^{\text{token is }\texttt{\textdollar}}_{i}$ $\displaystyle:=2\operatorname{ReLU}(z^{\text{is read key}}_{i}-z^{\text{read retr0 val}}_{i}).$ (119) $$

Here, we use coefficient $2$ to distinguish the output extraction stage from the execution stage.

### B.9 Generating next token

The next token to be generated by the Transformer $\varGamma$ is

$$ $\displaystyle\operatorname*{\arg\max}_{\sigma\in\{\mathtt{A}\mathtt{L},\mathtt {B}\mathtt{L},\mathtt{A}\mathtt{R},\mathtt{B}\mathtt{R},\mathtt{A}\mathtt{0}, \mathtt{B}\mathtt{0},\mathtt{A}\mathtt{1},\mathtt{B}\mathtt{1},\texttt{/}, \texttt{=},\texttt{-},\texttt{+},\texttt{@},\texttt{:},\mathtt{0},\mathtt{1}, \texttt{\textdollar}\}}z^{\text{token is }\sigma}_{|\boldsymbol{v}|-1}.$ (120) $$

The generation procedure stops upon the generation of the ending token $.(^2^22Nevertheless, the token $ in the prompt does not stop the generation procedure.)

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Please explain the aspect of universality of your construction mentioned above.

Could you please discuss in more detail what is the size of the constructed Transformer.

L.129: you write that you refer to the time complexity as the the time complexity on a random-access
machine (RAM). But this seems to be not true. Could you please explain this?

L.146: why is the embedding function, a function from $\Sigma$ and not from $\Sigma^+$ or $\Nat \times \Sigma$?

L. 158: You call: key map qry_{l,k}. It should be: key_{l,k}

L. 335: why do you define E(0) := ALALA1 and not as E(0) := ALA0ALA1 ?
soundness: 3
strengths: The computational power of Neural Networks, and especially of Transformers, studied in this work, is an important and interesting topic that has been studied for some time. The authors have shown new results in this field and improved previously known achievements, in particular those of Perez et al. (ICLR 2019 and JMLR 2021) and Merrill & Sabharwal (ICLR, 2024). While Perez et al. (2021) have shown that for any computable function $\varphi$ there exists a Transformer that computes the function, the submitted work proves that there exists a single finite sized (decoder-only) Transformer that, when fed with promptes corresponding to a function, is Turing complete. Moreover, the performance of prompting the single Transformer achieves the same precision complexity and almost the same chain-of-thought (CoT) complexity as the Transformers presented in previous works, which, however, were not universal.
summary: This is a theoretical work whose main contribution is the proof that there exists a finite-sized transformer such that for any computable function $\varphi$ there is a corresponding prompt such that, when concatenated with an input $x$, the transformer generates an output which encodes the value $\varphi(x)$. To show this result, the authors use a new model of computations, called in the paper two-tape Post-Turing machines (2-PTMs), which extends Wang's basic machines and is inspired by the Hennie–Stearns theorem showing that any multi-type Turing machine (TM) can be simulated by a two-tape TM whose running time increases only by a logarithmic factor. The authors also provide bounds on the size of the output generated by the transformer, which depends on the size of the input and the time complexity of the multi-type TM computing the function.
weaknesses: The topics discussed in the paper and the methods of proofs are not entirely new, and the main result, although it sheds new light on the issue of computability, is not groundbreaking in this field. Moreover, to claim that this work proves Turing completeness of prompting is in some sense an over interpretation of the achievements. First, although it is justified by the results of Hahn (2020) and others, a rather negative aspect of the results of this work is hidden in the fact that autoregressive generation has to process huge sequences of tokens (called in this and related works CoT). Second, to compute a function from the class TIME(t(n)), the constructed Transformer Γ needs $O(\log(n + t(n)))$ bits of precision. Thus, in this context, Γ is not universal in the sense that, for example, a Universal Turing machine is understood.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: I would love to better understand what about this result you think might be surprising. Before you proved the result, did you have any doubt it would hold? What aspects of Transformers did you imagine might make them less than Turing-complete, when given infinite CoT steps and an infinite context window?
soundness: 3
strengths: This paper is clearly written, and the technical details appear to be sound. The construction of the particular Transformer for simulating 2-PTMs is clever.
summary: This paper constructs a Transformer-like algorithm that, given an encoding of a particular two-tape Post-Turing machine, simulates the machine. The algorithm is "Transformer-like" in that it is a composition of a finite number of "layers," each of which has structure similar to that found in a Transformer (e.g., query, key, and value computations that feed into a (hard) attention mechanism). The authors conclude from this construction that "prompting is Turing-complete," i.e., that there exists a finite Transformer that can be prompted to efficiently simulate any program.
weaknesses: I am an outsider to this area, and am not confident in this evaluation. However, I found it difficult to understand the significance of this result. 

We, of course, already know that it is possible to unambiguously specify computations with strings in a finite alphabet. We also know that finite machines with infinite tapes can execute these computations. In some sense the "prompting paradigm" (use a string to tell a machine what we want it to do) is also just the "programming paradigm." So the real question is whether a Transformer can execute a program provided to it in its prompt, and it seems to me that the answer hinges on how you define "Transformer." As you vary the definition, you will be setting up different puzzles for yourself, regarding how to encode the various necessary operations (e.g., in this paper, Boolean logic, equality checks, farthest retrieval) within a "Transformer." Why is this particular model of Transformers interesting? 

It seems important for the model of the Transformer to reflect real-world Transformers in all essential respects; but in order to judge which respects are essential, more context is needed on what doubts or questions about (real-world) Transformers this research is meant to address. That is, a priori, why might someone *doubt* the existence of a Transformer that executes program instructions in its prompt? And does your theorem actually put those doubts to rest? For instance, if someone thinks Transformers are limited because they have finite context windows, this theorem will not dissuade them (it assumes infinite context windows). If someone thinks that somehow the "soft" nature of softmax attention limits Transformers' ability to correctly implement "hard" algorithms, this theorem will not persuade them otherwise (it assumes hard attention). And so on. What questions/doubts exactly is your theorem intending to settle? Is the model of Transformers that you propose sufficiently faithful to real Transformers to satisfyingly address those questions?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: What is the advantage of using a 2-PTM instead of a standard Turing machine in [1]?

[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.
soundness: 4
strengths: + The paper presents a new reduction that proves Turing-completeness of transformers with hardmax attention.
+ The authors deliver a thorough construction and proof for their Turing-completeness result.
summary: This paper demonstrates that a family of decoder-only transformers achieves Turing-completeness through appropriate prompting. The authors establish this by constructing transformers that can simulate a two-tape Post-Turing Machine (2-PTM), a model known to be Turing-complete. Their approach involves encoding 2-PTM programs and inputs into prompts, enabling the transformer to simulate the execution trace of the 2-PTM. A subsequent readout process extracts the final output of the 2-PTM from the transformer's output. The paper also provides complexity bounds for the chain-of-thought (CoT) steps required in the simulation, proving its efficiency.
weaknesses: - The paper lacks sufficient justification for the novelty of its results. The Turing-completeness of transformers with prompting appears to follow naturally from existing work. It’s well-known that a Universal Turing Machine (UTM) can simulate any Turing machine by encoding the machine as part of the input. Given prior work [1], which shows that transformers with hard attention are Turing-complete, it’s intuitive that a family of transformers can simulate a UTM. Consequently, encoding any Turing machine within a prompt for a transformer simulating a UTM to achieve Turing-completeness appears to be a straightforward implication.
- Regarding complexity, the simulation results presented do not appear groundbreaking. Previous work [2] establishes that there exists a UTM capable of simulating any Turing machine in $O(T(n)\log(T(n)))$ steps, given the machine halts within $T(n)$ steps. Since the simulation in [1] requires only a single transformer step per Turing machine step, it follows that [1]'s construction can also simulate within $O(T(n)\log(T(n)))$ steps. The authors should clarify why their new construction is necessary and how it extends or innovates beyond these established results.

[1] Pérez, J., Barceló, P., & Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75), 1-35.

[2] Hennie, F. C., & Stearns, R. E. (1966). Two-tape simulation of multitape Turing machines. Journal of the ACM (JACM), 13(4), 533-546.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Does it make sense to use a one-hot representation as the embedding (lines 781–782)? Since the Transformer embedding layer doesn’t use one-hot encoding, this appears to leave a gap in the proof to me.
soundness: 3
strengths: The paper provides a theoretical foundation for prompt engineering. It is well-written, with a clear structure and logical flow, making it a challenging yet engaging read.
summary: This paper establishes and proves that prompting is Turing-complete: there exists a finite-size Transformer such that, for any computable function, there is a corresponding prompt that enables the Transformer to compute that function.
Additionally, the paper demonstrates that prompting is efficiently universal, meaning a single finite-size Transformer can approximate the computational complexity of the entire class of unbounded-size Transformers.

To support this, the authors introduce two-tape Post–Turing machines (2-PTMs) as a basis for constructing the prompt, chain-of-thought (CoT), input tokenizer, and Transformer model. They further prove that 2-PTMs are Turing-complete and nearly as efficient as standard Turing machines (TMs). Specifically, 2-PTM is able to compute from input x（x is within the domain of \psi) to \psi(x), within at most O(t(n)logt(n)), i.e., only logarithmic slow down over TM.

These results provide a foundation for characterizing the CoT complexity and precision complexity of the constructed Transformer. Specifically, prompting a single Transformer can compute any TIME2(t(n)) function within O(t(n)) CoT steps and any TIME(t(n)) function within O(t(n)logt(n)) CoT steps. Prompting a single Transformer can achieve the same precision complexity as that of the entire class of Transformers.
weaknesses: There are a few minor typos to address. For instance, on line 158, the key map notation is mistakenly written as the query map notation, and on line 759, the first '1' should actually be '0'.

I have a question: does it make sense to use a one-hot representation as the embedding (lines 781–782)? Since the Transformer embedding layer doesn’t use one-hot encoding, this appears to leave a gap in the proof to me.

Meta-review: This paper proves that LLM prompting is Turing complete, extending theoretical understanding to a common one-model-many-task setting of LLMs. I am not an expert in this area and lean on the reviewers for decision making. The reviewers appreciated the importance, novelty and technical correctness of the paper.

Decision: Accept (Poster)