# The sharp constants in the Real Anisotropic Littlewood’s $4/3$ inequality

Nicolás Caro-Montoya  Departamento de Matemática
Universidade Federal de Pernambuco
Avenida Jornalista Aníbal Fernandes, S/N - Cidade Universitária
Recife/PE - Brasil - 50740-560<EMAIL_ADDRESS>and  Diana Serrano-
Rodríguez  Departamento de Matemáticas
Universidad Nacional de Colombia
Bogotá, Colombia - 111321<EMAIL_ADDRESS>Dedicated to the memory of
Jhazaira Mantilla Pérez

###### Abstract.

The Real Anisotropic Littlewood’s $4/3$ inequality is an extension of a famous
result obtained in 1930 by J. E. Littlewood. It asserts that (see [17]*Theorem
5.1) for $a,b\in(0,\infty)$, the following assertions are equivalent:

  * •

There is a constant $C_{a,b}^{\mathbb{R}}\geq 1$ such that

$\Biggl{(}\sum_{i=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{a}\biggr{)}^{b\times\frac{1}{a}}\Biggr{)}^{\frac{1}{b}}\leq
C_{a,b}^{\mathbb{R}}\lVert A\rVert$

for every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{R}$.

  * •

The exponents $a,b$ satisfy $(a,b)\in[1,\infty)\times[1,\infty)$ with

$\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}.$

Several authors have obtained optimal estimates of the best constant
$C_{a,b}^{\mathbb{R}}$, for diverse pairs of values $(a,b)$.

In this paper we provide the optimal values of $C_{a,b}^{\mathbb{R}}$ for all
admissible pair of values $(a,b)$. Furthermore, we provide new estimates for
$C_{a,b}^{\mathbb{C}}$, which are optimal for several pairs of values $(a,b)$.
As an application, we prove a variant (in the sense of [15]) of Khinchin’s
inequality for Steinhaus variables.

###### Key words and phrases:

Bilinear forms; Khinchin’s inequality; Littlewood’s $4/3$ inequality, Matrix
norms

###### 2020 Mathematics Subject Classification:

11Y60, 42B08, 46B09.

###### Contents

  1. 1 Introduction
  2. 2 The proof of the main result
  3. 3 Remarks on the complex case
  4. 4 Variants of Khinchin’s inequality for Steinhaus variables

##  1\. Introduction

The origins of the theory of absolutely summing multilinear operators are
linked to the so-called Littlewood’s $4/3$ inequality [11]; for a detailed
introduction to the theory of absolutely summing operators see [9]. On the
other hand, the multilinear theory of absolutely summing operators has been
recently explored in different contexts by several authors (see [3, 4, 5, 7,
13, 16, 17] and the references therein), with unexpected applications in other
fields such as Quantum Information Theory (more precisely, quantum XOR games),
Computational Learning Theory and results related to the study of Dirichlet
series (more precisely, questions concerning the $n$-dimensional Bohr radius;
see [2, 4, 12, 20]). These applications were achieved, among other techniques,
by the study of sharp constants for inequalities of the type Littlewood’s
$4/3$ (and its multilinear version, namely Bohnenblust–Hille’s inequality).
Driven by this, in the last decade several works have emerged that attempt to
study generalizations of Littlewood’s $4/3$ inequality to the multilinear
context and also to other sequence spaces (see [14, 18] and the references
therein).

All along this paper $\mathbb{K}$ stands for either $\mathbb{R}$ or
$\mathbb{C}$, and $c_{0}=c_{0}(\mathbb{K})$, the Banach space of null
sequences. By convention, when $a=\infty$, the sum $\bigl{(}\sum_{j}\lvert
x_{j}\rvert^{a}\bigr{)}^{1/a}$ represents the supremum of the values $\lvert
x_{j}\rvert$. In addition we define $f(\infty)\coloneq\lim_{s\to\infty}f(s)$
for any function $f$. We also define $1/0=\infty$ and $1/\infty=0$, and for
$s\geq 1$ we denote by $s^{\ast}$ the conjugate index of $s$, so that
$\frac{1}{s}+\frac{1}{s^{\ast}}=1$. Finally, we denote the canonical sequence
of vectors of $c_{0}$ by $(e_{k})_{k=1}^{\infty}$.

Littlewood’s $4/3$ inequality [11] asserts that there is a constant
$L_{\mathbb{K}}\geq 1$ such that

$\Biggl{(}\sum_{i,j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{\frac{4}{3}}\Biggr{)}^{\frac{3}{4}}\leq
L_{\mathbb{K}}\lVert A\rVert$

for every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{K}$,
where

$\lVert
A\rVert\coloneq\sup\Biggl{\\{}\bigg{\lvert}\sum_{i,j=1}^{\infty}A(e_{i},e_{j})x_{i}y_{j}\bigg{\rvert}\colon\lvert
x_{i}\rvert,\lvert y_{j}\rvert\leq 1\ \textnormal{for all}\ i,j\Biggr{\\}}$

It is well known that the exponent $4/3$ is optimal, and it is shown in [10]
that the value $L_{\mathbb{R}}=\sqrt{2}$ is also optimal. For complex scalars
we only know that $L_{\mathbb{C}}\leq 2/\sqrt{\pi}$.

However, the optimality feature of the exponent $4/3$ is related to the
specific configuration of this inequality. A key issue in the theory has been
to investigate optimality ranges for summing inequalities involving
anisotropic exponents. More specifically, the objective of study is to control

(1.1) $\Biggl{(}\sum_{i=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{a}\biggr{)}^{\frac{1}{a}\times
b}\Biggr{)}^{\frac{1}{b}}$

for all norm-$1$ continuos bilinear form $A\colon c_{0}\times
c_{0}\to\mathbb{K}$. This problem has been addressed through several
approaches permeating the theory and the definitive answer was given over the
past decade.

The following Anisotropic Littlewood’s $4/3$ inequality is proved in
[1]*Theorems 6.3:

######  Theorem 1.1.

Let $a,b\in[1,2]$. The following assertions are equivalent:

  * •

There is a constant $C_{a,b}^{\mathbb{K}}\geq 1$ such that

$\Biggl{(}\sum_{i=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{a}\biggr{)}^{b\times\frac{1}{a}}\Biggr{)}^{\frac{1}{b}}\leq
C_{a,b}^{\mathbb{K}}\lVert A\rVert$

for every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{K}$.

  * •

The values $a$ and $b$ satisfy

(1.2) $\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}.$

Observe that by taking $a=b=4/3$ in Theorem 1.1 one recovers Littlewood’s
$4/3$ inequality.

About the constants, for complex scalars, the determination of the exact
values of the optimal constants involved is probably a difficult task. In this
case, the only known optimal estimates are (see [1]*Remark 6.4 and [6]*page
31):

$\displaystyle C_{1,2}^{\mathbb{C}}$
$\displaystyle=C_{2,1}^{\mathbb{C}}=\frac{2}{\sqrt{\pi}};$ $\displaystyle
C_{2,2}^{\mathbb{C}}$ $\displaystyle=1,$

and, in general, if $1\leq a,b\leq 2$ with
$\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}$, we have

$1\leq
C_{a,b}^{\mathbb{C}}\leq\biggl{(}\frac{4}{\pi}\biggr{)}^{\frac{1}{a}+\frac{1}{b}-1}.$

For the case of real scalars we have:

######  Theorem 1.2 ([1]*Theorem 6.3).

Let $1\leq a,b\leq 2$ with $\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}$. Then for
every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{R}$ we have

$\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}\leq
2^{\frac{1}{b}+\frac{1}{a}-1}\lVert A\rVert.$

Moreover, the constant $2^{\frac{1}{a}+\frac{1}{b}-1}$ is optimal.

Condition “$1\leq a,b\leq 2$” in Theorem 1.1 can be dropped. In fact,
[17]*Theorem 5.1 provides the following definitive result:

######  Theorem 1.3.

Let $a,b\in(0,\infty)$. The following assertions are equivalent:

  * •

There is a constant $C_{a,b}^{\mathbb{K}}\geq 1$ such that

(1.3) $\Biggl{(}\sum_{i=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{a}\biggr{)}^{b\times\frac{1}{a}}\Biggr{)}^{\frac{1}{b}}\leq
C_{a,b}^{\mathbb{K}}\lVert A\rVert$

for every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{K}$.

  * •

The exponents $a,b$ satisfy $(a,b)\in[1,\infty)\times[1,\infty)$ with

$\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}.$

######  Remark 1.4.

We stress that Theorem 1.3 can be stated even in the case that $a$ or $b$ are
equal to $\infty$. This fact will be evident in the results we are going to
demonstrate in the following section.

######  Remark 1.5.

Observe that, by the inclusion of the $\ell_{p}$ spaces, since
$C_{2,2}^{\mathbb{K}}=1$, if $a\geq 2$ and $b\geq 2$, we have that the optimal
constant $C_{a,b}^{\mathbb{K}}$ is $1$ (see Figure 1).

These remarks, and the complete generality of Theorem 1.3, lead us to pose the
following questions:

######  Problem 1 (see Figure 1).

What are the optimal values of $C_{a,b}^{\mathbb{R}}$ in (1.3) in the cases
$(a,b)\in[1,2]\times[2,\infty]$ and $(a,b)\in[2,\infty]\times[1,2]$?

######  Problem 2.

What are the optimal values of $C_{a,b}^{\mathbb{C}}$ in (1.3), when the
exponents $a,b$ satisfy $(a,b)\in[1,\infty]\times[1,\infty]$ and
$\frac{1}{a}+\frac{1}{b}\leq\frac{3}{2}$?

Figure 1. Illustration of Theorem 1.3: the curve passing through the points
$(1,2)$ and $(2,1)$ is the hyperbola $b=\frac{2a}{3a-2}$. Region 0 corresponds
to non-admissible exponents in the anisotropic Littlewood’s $4/3$ inequality.
Region I correspond to Theorem 1.2, so that the value of the optimal constant
is $2^{\frac{1}{a}+\frac{1}{b}-1}$ in this case. Region II correspond to
Remark 1.5; in this region the optimal constant has always value $1$. Region
III corresponds to points for which the optimal constant is unknown.

In this paper we solve Problem 1 (and partially Problem 2), thus providing a
complete description of the constants in the Real Anisotropic Littlewood’s
$4/3$ inequality:

######  Theorem 1.6.

Let $a,b\in[1,\infty]$ with $\frac{1}{b}+\frac{1}{a}\leq\frac{3}{2}$. Then for
every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{R}$ we have

$\Biggl{(}\sum_{k=1}^{N}\biggl{(}\sum_{j=1}^{N}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}\leq
2^{\max\\{0,\frac{1}{b}+\frac{1}{a}-1\\}}\lVert A\rVert.$

Moreover, the constant $2^{\max\\{0,\frac{1}{b}+\frac{1}{a}-1\\}}$ is optimal.

In order to better understand this result, we divide the region of admissible
exponents into the following $4$ subregions (see Figure 2):

  1. (RI)

Points $(a,b)$ be such that $1\leq b,a\leq 2$ and
$\frac{1}{b}+\frac{1}{a}\leq\frac{3}{2}$.

  2. (RII)

The infinite region of points $(a,b)\in[1,\infty]\times[a^{\ast},\infty]$.

  3. (RIII)

The infinite region of points $(a,b)\in[2,\infty]\times[1,a^{\ast}]$.

  4. (RIV)

The infinite region of points $(a,b)\in[1,2]\times[2,a^{\ast}]$.

Figure 2. Illustration of Theorem 1.6: regions (RI), (RIII) and (RIV)
correspond to the value $2^{\frac{1}{a}+\frac{1}{b}-1}$ for the optimal
constant, whereas region (RII) corresponds to points for which the optimal
constant is $1$.

This paper is organized as follows: in Section 2 we present the proof of our
main result, Theorem 1.6, by using a variant of Khinchin’s inequality [15]
together with techniques of interpolation; this result gives a complete
description of the constants in the Real Anisotropic Littlewood’s $4/3$
inequality, thus completely solving Problem 1. In Section 3 we extend the
ideas of Section 2 to the setting of complex scalars, which allow us to
partially solve Problem 2. Finally, as an application of the techniques from
Section 3, we prove in Section 4 a variant (in the sense of [15]) of
Khinchin’s inequality for Steinhaus variables.

##  2\. The proof of the main result

We need the following variant of the Khinchin inequality of [15]. The proof
strongly uses the so-called Contraction Principle (see [9]*Theorem 12.2).

######  Proposition 2.1 ([15]*Lemma 1 and Proposition 1).

Let $N$ be a positive integer and $(a_{i})_{i=1}^{N}\in\mathbb{K}^{N}$ be a
sequence of scalars. If $r\in[2,\infty]$, then

(2.1) $\biggl{(}\sum_{i=1}^{N}\lvert
a_{i}\rvert^{r}\biggr{)}^{\frac{1}{r}}\leq
2^{\frac{1}{r}}\int_{0}^{1}\bigg{\lvert}\sum_{i=1}^{N}r_{i}(t)a_{i}\bigg{\rvert}\,dt$

and the estimate $2^{1/r}$ is optimal.

Above, as usual, $(r_{i}\colon[0,1]\to\mathbb{R})_{i=1}^{\infty}$ is the
sequence of independent and identically distributed random variables defined
by

(2.2) $r_{i}(t)\coloneq\operatorname{sign}\bigl{(}\sin(2^{i}\pi t)\bigr{)},$

the so-called Rademacher _functions_.

In order to prove our main result, we start with the following extremal
particular cases:

######  Lemma 2.2.

Let $a\in[2,\infty]$. Then for every continuos bilinear form $A\colon
c_{0}\times c_{0}\to\mathbb{R}$ we have

$\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{1/a}\leq 2^{\frac{1}{a}}\lVert A\rVert.$

###### Proof.

Let $N$ be a positive integer. Observe that, by Proposition 2.1, for all
$a\geq 2$ we have

$\sum_{k=1}^{N}\biggl{(}\sum_{j=1}^{N}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{1/a}\leq
2^{\frac{1}{a}}\sum_{k=1}^{N}\int_{0}^{1}\bigg{\lvert}\sum_{j=1}^{N}r_{j}(t)A(e_{k},e_{j})\bigg{\rvert}\,dt.$

Moreover,

(2.3) $\displaystyle
2^{\frac{1}{a}}\sum_{k=1}^{N}\int_{0}^{1}\bigg{\lvert}\sum_{j=1}^{N}r_{j}(t)A(e_{k},e_{j})\bigg{\rvert}\,dt$
$\displaystyle\leq
2^{\frac{1}{a}}\int_{0}^{1}\sum_{k=1}^{N}\bigg{\lvert}\sum_{j=1}^{N}r_{j}(t)A(e_{k},e_{j})\bigg{\rvert}\,dt$
$\displaystyle=2^{\frac{1}{a}}\int_{0}^{1}\sum_{k=1}^{N}\Bigg{\lvert}A\biggl{(}e_{k},\sum_{j=1}^{N}r_{j}(t)e_{j}\biggr{)}\Bigg{\rvert}\,dt$
$\displaystyle\leq
2^{\frac{1}{a}}\int_{0}^{1}\Bigg{\lVert}A\biggl{(}\cdot\,,\sum_{j=1}^{N}r_{j}(t)e_{j}\biggr{)}\Bigg{\rVert}\,dt$
$\displaystyle\leq 2^{\frac{1}{a}}\lVert A\rVert.\qed$

######  Lemma 2.3.

Let $a\in[2,\infty]$. Then for every continuos bilinear form $A\colon
c_{0}\times c_{0}\to\mathbb{R}$ we have

$\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{a^{\ast}/a}\Biggr{)}^{1/a^{\ast}}\leq\lVert
A\rVert.$

###### Proof.

Observe that the extreme case $a=\infty$ is given by Lemma 2.2. On the other
hand, it is well known that for every continuos bilinear form $A\colon
c_{0}\times c_{0}\to\mathbb{R}$

$\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{2}\biggr{)}\Biggr{)}^{1/2}\leq\lVert A\rVert.$

Let

$\theta_{0}\coloneq\frac{a-2}{a}.$

Note that $\theta_{0}\in(0,1)$ ; since

$\displaystyle\frac{1}{a}$
$\displaystyle=\frac{\theta_{0}}{\infty}+\frac{1-\theta_{0}}{2};$
$\displaystyle\frac{1}{a^{\ast}}$
$\displaystyle=\frac{\theta_{0}}{1}+\frac{1-\theta_{0}}{2},$

a simple interpolation argument yields

$\displaystyle\Biggl{(}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{a^{\ast}/a}\Biggr{)}^{1/a^{\ast}}$
$\displaystyle\leq\biggl{(}\sum_{k=1}^{\infty}\sup_{j}\lvert
A(e_{k},e_{j})\rvert\biggr{)}^{\frac{a-2}{a}}\Biggl{(}\biggl{[}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{2}\biggr{)}\biggr{]}^{\frac{1}{2}}\Biggr{)}^{\frac{2}{a}}$
$\displaystyle\leq\lVert A\rVert.\qed$

Now we are ready to prove the main result of this work.

###### Proof of Theorem 1.6.

Let $b\in[1,\infty]$ and $a\in[1,\infty]$, with
$\frac{1}{b}+\frac{1}{a}\leq\frac{3}{2}.$ If $1\leq b,a\leq 2$, the result
follows from Theorem 1.2 (these points correspond to region (RI)).

Suppose at first that $1\leq\frac{1}{b}+\frac{1}{a}\leq\frac{3}{2}$ (i.e.,
$\frac{1}{a^{\ast}}\leq\frac{1}{b}\leq\frac{3}{2}-\frac{1}{a}$). Thus, if
$a\in[2,\infty]$ , then we have $b\in[1,a^{\ast}]$ (these points correspond to
region (RIII)). If

$\theta_{1}\coloneq 1-\frac{a}{b^{\ast}},$

then we have $\theta_{1}\in(0,1)$; moreover, since

$\frac{1}{b}=\frac{\theta_{1}}{1}+\frac{1-\theta_{1}}{a^{\ast}},$

an interpolation argument together with Lemmas 2.2 and 2.3 yields

(2.4) $\left\\{\begin{aligned}
&\quad\Biggl{(}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}\\\\[5.69054pt]
&\leq\Biggl{(}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{1/a}\Biggr{)}^{1-\frac{a}{b^{\ast}}}\times\
\ \Biggl{(}\biggr{[}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{a^{\ast}/a}\biggr{]}^{1/a^{\ast}}\Biggr{)}^{\frac{a}{b^{\ast}}}\\\\[5.69054pt]
&\leq\bigl{(}2^{\frac{1}{a}}\lVert
A\rVert\bigr{)}^{1-\frac{a}{b^{\ast}}}\cdot(\lVert
A\rVert)^{\frac{a}{b^{\ast}}}\\\
&=\bigl{(}2^{\frac{1}{a}}\bigr{)}^{1-\frac{a}{b^{\ast}}}\lVert A\rVert\\\
&=2^{\frac{1}{b}+\frac{1}{a}-1}\lVert A\rVert.\end{aligned}\right.$

Now, if $a\in[1,2]$ (recall that
$\frac{1}{a^{\ast}}\leq\frac{1}{b}\leq\frac{3}{2}-\frac{1}{a}$), then we have
$b\in[2,a^{\ast}]$ (these points correspond to region (RIV)). Thus, if
$b\neq\infty$, then from Minkowski’s inequality and (2.4) we get

$\displaystyle\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}$
$\displaystyle\leq\Biggl{(}\sum_{j=1}^{\infty}\biggr{(}\sum_{k=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{b}\biggr{)}^{a/b}\Biggr{)}^{1/a}$ $\displaystyle\leq
2^{\frac{1}{a}+\frac{1}{b}-1}\lVert A\rVert.$

The extreme case $b=\infty$ and $a=1$ follows trivially from

$\sup_{k}\sum_{j=1}^{\infty}\lvert A(e_{k},e_{j})\rvert\leq\lVert A\rVert.$

On the other hand, the bilinear form

$A_{0}(x,y)=x_{1}y_{1}+x_{1}y_{2}+x_{2}y_{1}-x_{2}y_{2}$

satisfies $\lVert A_{0}\rVert=2$ and

$\Biggl{(}\sum_{k=1}^{2}\biggr{(}\sum_{j=1}^{2}\lvert
A_{0}(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}=2^{\frac{1}{b}+\frac{1}{a}-1}\lVert
A_{0}\rVert$

(see [10]), which shows that the value $2^{\frac{1}{b}+\frac{1}{a}-1}$ cannot
be improved.

Finally, for the case $b\in[1,\infty]$ and $a\in[1,\infty]$, with
$\frac{1}{b}+\frac{1}{a}\leq 1$ (i.e., $\frac{1}{b}\leq\frac{1}{a^{\ast}}$),
if we have $a\in[1,\infty]$ then $b\in[a^{\ast},\infty]$ (these points
correspond to region (RII)), and thus

$\displaystyle\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{b/a}\Biggr{)}^{1/b}$
$\displaystyle\leq\Biggl{(}\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{a^{\ast}/a}\Biggr{)}^{1/a^{\ast}}$
$\displaystyle\leq\lVert A\rVert.$

Thus, in this case the optimal constant is $1$. ∎

##  3\. Remarks on the complex case

In this section we partially replicate, for the case of complex scalars, the
results obtained in the previous section. First, we have the following
estimate:

######  Lemma 3.1.

Let $a\in[2,\infty]$. Then for every continuos bilinear form $A\colon
c_{0}\times c_{0}\to\mathbb{C}$ we have

$\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{1/a}\leq\biggl{(}\frac{4}{\pi}\biggr{)}^{\frac{1}{a}}\lVert
A\rVert.$

###### Proof.

Observe that by Proposition 2.1, for $a=\infty$:

$\sum_{k=1}^{\infty}\sup_{j}\lvert A(e_{k},e_{j})\rvert\leq\lVert A\rVert.$

Moreover, it is known that (see [6]*page 31)

$\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{2}\biggr{)}^{1/2}\leq\biggl{(}\frac{4}{\pi}\biggr{)}^{\frac{1}{2}}\lVert
A\rVert.$

Interpolating with $\theta=\frac{2}{a}$ we have

$\displaystyle\sum_{k=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{1/a}$
$\displaystyle\leq\Biggl{(}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{2}\biggr{)}^{1/2}\Biggr{)}^{\theta}\biggr{(}\sum_{k=1}^{\infty}\sup_{j}\lvert
A(e_{k},e_{j})\rvert\biggr{)}^{1-\theta}$
$\displaystyle\leq\Biggl{(}\biggl{(}\frac{4}{\pi}\biggr{)}^{\frac{1}{2}}\lVert
A\rVert\Biggr{)}^{\frac{2}{a}}\lVert
A\rVert^{\frac{a-2}{a}}=\biggl{(}\frac{4}{\pi}\biggr{)}^{\frac{1}{a}}\lVert
A\rVert.\qed$

By mimicking the proof of Lemma 2.3 and Theorem 1.6 we get, respectively:

######  Lemma 3.2.

Let $a\in[2,\infty]$. Then for every continuos bilinear form $A\colon
c_{0}\times c_{0}\to\mathbb{C}$ we have

$\Biggl{(}\sum_{k=1}^{\infty}\biggr{(}\sum_{j=1}^{\infty}\lvert
A(e_{k},e_{j})\rvert^{a}\biggr{)}^{a^{\ast}/a}\Biggr{)}^{1/a^{\ast}}\leq\lVert
A\rVert.$

######  Theorem 3.3.

Let $a,b\in[1,\infty]$ with $\frac{1}{b}+\frac{1}{a}\leq\frac{3}{2}$. There is
a constant $C_{a,b}^{\mathbb{C}}\geq 1$ such that

$\Biggl{(}\sum_{i=1}^{\infty}\biggl{(}\sum_{j=1}^{\infty}\lvert
A(e_{i},e_{j})\rvert^{a}\biggr{)}^{b\times\frac{1}{a}}\Biggr{)}^{\frac{1}{b}}\leq
C_{a,b}^{\mathbb{C}}\lVert A\rVert$

for every continuos bilinear form $A\colon c_{0}\times c_{0}\to\mathbb{C}$.
Moreover, if $b\leq a$, then we have

$1\leq C_{b,a}^{\mathbb{C}}\leq
C_{a,b}^{\mathbb{C}}\leq\biggl{(}\frac{4}{\pi}\biggr{)}^{\max\\{0,\frac{1}{a}+\frac{1}{b}-1\\}}.$

In particular, for $a,b\in[1,\infty]$ with $\frac{1}{b}+\frac{1}{a}\leq 1$ we
have $C_{a,b}^{\mathbb{C}}=1$.

Figure 3. Illustration of Theorem 3.3: region II corresponds to points for
which the optimal constant is $1$. Region I corresponds to points for which
the optimal constant (in the complex case) is unknown, except for
$(a,b)=(1,2)$ and $(2,1)$, where we have
$C_{a,b}^{\mathbb{C}}=\frac{2}{\sqrt{\pi}}$.

##  4\. Variants of Khinchin’s inequality for Steinhaus variables

In this section, among other results, we obtain a version of Proposition 2.1
for Steinhaus variables.

Observe that the optimal constant in Proposition 2.1 coincides with the
optimal constants $C_{1,r}^{\mathbb{R}}$ and $C_{r,1}^{\mathbb{R}}$ for all
$r\in[2,\infty]$.

Khinchin’s inequality for Steinhaus variables plays a crucial role in the
improvement of estimates for the constants in inequalities of the type
Littlewood’s $4/3$ (and their extended multilinear versions) for complex
scalars (see [1, 8]). For a very recent approach to Khinchin’s inequality we
refer to [19].

In the previous section we do not provide a version of Proposition 2.1 for
Steinhaus variables because its proof strongly uses the Contraction Principle.
Such a principle is stated only for randomized sums (independent symmetric
real-valued random variables), and we do not know if a similar principle holds
for independent symmetric complex-valued random variables.

In contrast, as an application of the methods from the previous section, we
obtain a version of Proposition 2.1 for Steinhaus variables with optimal
constant coinciding with the optimal constants $C_{1,r}^{\mathbb{C}}$ and
$C_{r,1}^{\mathbb{C}}$, for all $r\in[2,\infty]$, as in the case of Rademacher
functions. Such result is achieved by using ideas from [8], where a type of
Khinchine’s inequality previously developed by R. Blei is studied.

It is well known that, by considering the dyadic expansion of $2^{N}t$ for
each $t\in[0,1]$, one can prove the equality

$\int_{[0,1]}\
\bigg{\lvert}\sum_{i=1}^{N}r_{i}(t)a_{i}\bigg{\rvert}\,dt=\frac{1}{2^{N}}\sum_{\bm{\eta}\in\\{1,-1\\}^{N}}\bigg{\lvert}\sum_{j=1}^{N}\eta_{j}a_{j}\bigg{\rvert},$

where the functions $r_{i}$ are given by (2.2). Thus, inequality (2.1) from
Proposition 2.1 can be rewritten as

(4.1) $\biggl{(}\sum_{j=1}^{N}\lvert
a_{j}\rvert^{r}\biggr{)}^{\frac{1}{r}}\leq
2^{\frac{1}{r}}\Biggl{(}\frac{1}{2^{N}}\sum_{\bm{\eta}\in\\{1,-1\\}^{N}}\bigg{\lvert}\sum_{j=1}^{N}\eta_{j}a_{j}\bigg{\rvert}\Biggr{)}$

for all $r\in[2,\infty]$, and for all sequences of scalars
$(a_{j})_{j=1}^{N}\in\mathbb{K}^{N}$ and all positive integers $N$.

The counterpart for the average

$\frac{1}{2^{N}}\sum_{\bm{\eta}\in\\{1,-1\\}^{N}}\bigg{\lvert}\sum_{j=1}^{N}\eta_{j}a_{j}\bigg{\rvert}$

in the complex framework is

(4.2)
$\biggl{(}\frac{1}{2\pi}\biggr{)}^{N}\int_{0}^{2\pi}\dotsi\int_{0}^{2\pi}\bigg{\lvert}\sum_{j=1}^{N}a_{j}e^{it_{j}}\bigg{\rvert}\,dt_{1}\dotsb
dt_{N}.$

For the sake of simplicity we shall denote (4.2) by

(4.3)
$\mathbb{E}\bigg{\lvert}\sum_{j=1}^{N}a_{j}\varepsilon_{j}\bigg{\rvert},$

where $\varepsilon_{j}$ are Steinhaus variables, that is, random variables
uniformly distributed on the complex unit circle. Our goal is to prove the
following version of Proposition 2.1 for Steinhaus variables:

######  Theorem 4.1.

Let $r\in[2,\infty]$. There is a (optimal) constant $C_{r}\geq 1$ such that

(4.4) $\biggl{(}\sum_{n=1}^{N}\lvert
a_{n}\rvert^{r}\biggr{)}^{\frac{1}{r}}\leq
C_{r}\biggl{(}\mathbb{E}\bigg{\lvert}\sum_{n=1}^{N}a_{n}\varepsilon_{n}\bigg{\rvert}\biggr{)}$

for every positive positive integer $N$ and for all sequences of scalars
$(a_{j})_{j=1}^{N}\in\mathbb{K}^{N}$, where
$\varepsilon_{1},\dotsc,\varepsilon_{n}$ are Steinhaus variables. Moreover,

$C_{r}=C_{1,r}^{\mathbb{C}}=C_{r,1}^{\mathbb{C}},$

for all $r\in[2,\infty]$.

In what follows we state a Khinchine-type inequality that extends and unifies
inequalities (1.1) and (4.4). First, we need to introduce some notation and
results.

For each integer $M\geq 2$, we define

$\displaystyle T_{M}$
$\displaystyle\coloneq\bigl{\\{}\exp\bigl{(}\tfrac{2j\pi}{M}i\bigr{)}\colon
j=0,\dotsc,M-1\bigr{\\}};$ $\displaystyle T_{\infty}$
$\displaystyle\coloneq\bigl{\\{}\exp(ti)\colon t\in[0,2\pi)\bigr{\\}},$ and
$\displaystyle D_{M}$ $\displaystyle\coloneq\operatorname{conv}(T_{M});$
$\displaystyle D_{\infty}$
$\displaystyle\coloneq\operatorname{conv}(T_{\infty}),$

where $\operatorname{conv}$ denotes the convex hull. Observe that $D_{\infty}$
is the closed unit disk, and that $D_{M}\subseteq D_{\infty}$. Obviously,
$D_{M}$ is a convex and closed absorbing set in $\mathbb{C}$.

Let $N$ and $M$ be positive integers, with $M\geq 3$. For any bilinear form
$A\colon\mathbb{C}^{N}\times\mathbb{C}^{N}\to\mathbb{C}$ we define the norm

$\lVert A\rVert_{M}\coloneq\sup\\{\lvert A(x,y)\rvert\colon y\in
T_{M}^{N};\lvert x_{i}\rvert\leq 1\ \textnormal{for}\ i=1,\dotsc,N\\}.$

The following basic result provides estimates for the $\sup$-norm $\lVert
A\rVert$:

######  Theorem 4.2 ([8]*Theorem 2.3).

Let $N,M$ be positive integers, with $M\geq 3$. Then

$\lVert A\rVert_{M}\leq\lVert A\rVert\leq R_{M}^{-1}\lVert A\rVert_{M}$

for all bilinear forms
$A\colon\mathbb{C}^{N}\times\mathbb{C}^{N}\to\mathbb{C}$, where

$R_{M}\coloneq\Biggl{[}\frac{1}{2}+\frac{1}{2}\cos\biggr{(}\frac{2\pi}{M}\biggr{)}\Biggr{]}^{\frac{1}{2}}.$

For each $M\geq 2$, let

$\Omega_{M}\coloneq\biggl{\\{}\frac{2j\pi}{M}\colon
j=0,\dotsc,M-1\biggr{\\}}.$

Let $(a_{n})_{n=1}^{N}\in\mathbb{K}^{N}$ be a sequence of scalars, and let
$M\geq 2$. We define

$E_{M}\bigl{(}(a_{n})_{n=1}^{N}\bigr{)}\coloneq\biggr{(}\frac{1}{M}\biggr{)}^{N}\sum_{\bm{\beta}\in\Omega_{M}^{N}}\bigg{\lvert}\sum_{n=1}^{N}a_{n}e^{i\beta_{n}}\bigg{\rvert}.$

Using the Dominated Convergence Theorem it is possible to prove that

$\lim_{M\to\infty}E_{M}\bigl{(}(a_{n})_{n=1}^{N}\bigr{)}=\mathbb{E}\bigg{\lvert}\sum_{n=1}^{N}a_{n}\varepsilon_{n}\bigg{\rvert}.$

We need the following auxiliary result:

######  Lemma 4.3 ([8]*Lemma 2.4).

Let $(a_{n})_{n=1}^{N}\in\mathbb{K}^{N}$ be a sequence of scalars, and let
$M\geq 2$. Then

$E_{M}\bigl{(}(a_{n})_{n=1}^{N}\bigr{)}=E_{M}\bigl{(}(a_{n}e^{is_{n}})_{n=1}^{N}\bigr{)}$

for all $s_{1},\dotsc,s_{N}\in\Omega_{M}$.

Now we are ready to state and prove the announced extension of Khinchine’s
inequality, for $r\in[2,\infty]$, that extends and unifies inequalities (1.1)
and (4.4). We emphasize that this result is already known for $r=2$; see
[6]*Chapter II: Section 6.

######  Theorem 4.4 (Blei–Khinchine inequality).

Let $r\in[2,\infty]$. For every $M\geq 2$, there is a (optimal) constant
$\mathcal{B}_{M,r}$ such that

(4.5) $\biggl{(}\sum_{n=1}^{N}\lvert
a_{n}\rvert^{r}\biggr{)}^{1/r}\leq\mathcal{B}_{M,r}\cdot
E_{M}\bigl{(}(a_{n})_{n=1}^{N}\bigr{)},$

for every positive integer $N$ and all sequences of scalars
$(a_{j})_{j=1}^{N}\in\mathbb{K}^{N}$. Moreover, for all $M\geq 3$ we have

(4.6) $\mathcal{B}_{M,r}\leq C_{1,r}^{\mathbb{C}}\cdot R_{M}^{-1},$

where

$R_{M}\coloneq\Biggl{[}\frac{1}{2}+\frac{1}{2}\cos\biggr{(}\frac{2\pi}{M}\biggr{)}\Biggr{]}^{\frac{1}{2}}.$

###### Proof.

The case $M=2$ is precisely the inequality (4.1), so we only need to prove the
case $M\geq 3$. Let $(a_{n})_{n=1}^{N}\in\mathbb{K}^{N}$ be a sequence of
scalars, such that $E_{M}\bigl{(}(a_{n})_{n=1}^{N}\bigr{)}=1$. Then, by Lemma
4.3,

$E_{M}\bigl{(}(a_{n}e^{is_{n}})_{n=1}^{N}\bigr{)}=\biggl{(}\frac{1}{M}\biggr{)}^{N}\sum_{\bm{\beta}\in\Omega_{M}^{N}}\bigg{\lvert}\sum_{n=1}^{N}a_{n}e^{is_{n}}e^{i\beta_{n}}\bigg{\rvert}=1$

for all $s_{1},\dotsc,s_{N}\in\Omega_{M}$. Thus, for all
$w_{1},\dotsc,w_{N}\in T_{M}$ we have

$\biggl{(}\frac{1}{M}\biggr{)}^{N}\sum_{\bm{t}\in
T_{M}^{N}}\bigg{\lvert}\sum_{n=1}^{N}a_{n}w_{n}t_{n}\bigg{\rvert}=1.$

Fix an enumeration of the set $T_{M}^{N}$, say
$\bm{\tau^{(1)}},\dotsc,\bm{\tau^{(M^{N})}}$, where
$\bm{\tau^{(i)}}=(\tau_{1}^{(i)},\dotsc,\tau_{N}^{(i)})$ for each $i$. In this
way, the equality above can be rewritten as

(4.7)
$\biggl{(}\frac{1}{M}\biggr{)}^{N}\sum_{i=1}^{M^{N}}\bigg{\lvert}\sum_{n=1}^{N}a_{n}\tau_{n}^{(i)}w_{n}\bigg{\rvert}=1,$

for all $w_{1},\dotsc,w_{N}\in T_{M}$.

Consider the bilinear form
$A\colon\mathbb{C}^{M^{N}}\times\mathbb{C}^{N}\to\mathbb{C}$ given by

$A(e_{i},e_{n})=\frac{a_{n}\tau_{n}^{(i)}}{M^{N}}\quad(i\in\\{1,\dotsc,M^{N}\\}\
;\ n\in\\{1,\dotsc,N\\}).$

We claim that $\lVert A\rVert_{M}\leq 1$. In fact, by using Hölder’s
inequality together with equality (4.7) we get

$\displaystyle\bigg{\lvert}\sum_{i=1}^{M^{N}}\sum_{n=1}^{N}A(e_{i},e_{n})w_{n}z_{i}\bigg{\rvert}$
$\displaystyle=\bigg{\lvert}\sum_{i=1}^{M^{N}}\sum_{n=1}^{N}\frac{a_{n}\tau_{n}^{(i)}}{M^{N}}w_{n}z_{i}\bigg{\rvert}$
$\displaystyle\leq\Biggl{(}\sum_{i=1}^{M^{N}}\bigg{\lvert}\sum_{n=1}^{N}\frac{a_{n}\tau_{n}^{(i)}}{M^{N}}w_{n}\bigg{\rvert}\Biggr{)}\cdot\sup_{1\leq
i\leq M^{N}}\lvert z_{i}\rvert$
$\displaystyle\leq\biggl{(}\frac{1}{M}\biggr{)}^{N}\sum_{i=1}^{M^{N}}\bigg{\lvert}\sum_{n=1}^{N}a_{n}\tau_{n}^{(i)}w_{n}\bigg{\rvert}$
$\displaystyle=1$

for all $w_{1},\dotsc,w_{N}\in T_{M}$ and all
$z_{1},\dotsc,z_{M^{N}}\in\mathbb{C}$ with $\sup_{1\leq i\leq M^{N}}\lvert
z_{i}\rvert\leq 1$. Therefore $\lVert A\rVert_{M}\leq 1$. Moreover, if
$r\in[2,\infty]$, then by using Theorems 1.3 and 4.2 and the above norm
estimate we obtain

$\displaystyle\biggl{(}\sum_{n=1}^{N}\lvert a_{n}\rvert^{r}\biggr{)}^{1/r}$
$\displaystyle=\Biggl{[}\sum_{n=1}^{N}\biggl{(}\sum_{i=1}^{M^{N}}\bigg{\lvert}\biggl{(}\frac{1}{M}\biggr{)}^{N}a_{n}\tau_{n}^{(i)}\bigg{\rvert}\biggr{)}^{r}\Biggr{]}^{\frac{1}{r}}$
$\displaystyle=\Biggl{[}\sum_{n=1}^{N}\biggl{(}\sum_{i=1}^{M^{N}}\lvert
A(e_{i},e_{n})\rvert\biggr{)}^{r}\Biggr{]}^{\frac{1}{r}}$ $\displaystyle\leq
C_{1,r}^{\mathbb{C}}\lVert A\rVert$ $\displaystyle\leq
C_{1,r}^{\mathbb{C}}\cdot R_{M}^{-1}\lVert A\rVert_{M}$ $\displaystyle\leq
C_{1,r}^{\mathbb{C}}\cdot R_{M}^{-1}.$

Thus, the inequality follows and

$\mathcal{B}_{M,r}\leq C_{1,r}^{\mathbb{C}}\cdot R_{M}^{-1},$

for all $r\in[2,\infty]$, and $M\geq 3$, as claimed. ∎

Now we can easily prove the main result of this section:

###### Proof of Theorem 4.1.

Taking $M\to\infty$ in Theorem 4.4, and using that $R_{M}\to 1$, we obtain the
inequality (4.4), with the estimate

$C_{r}\leq C_{1,r}^{\mathbb{C}}$

for all $r\in[2,\infty]$.

On the other hand, since $r>1$, Theorem 3.3 implies

$C_{1,r}^{\mathbb{C}}\leq C_{r,1}^{\mathbb{C}}$

for all $r\in[2,\infty]$.

Finally, we can repeat the proof of Lemma 2.2 in the case of complex scalars,
by just replacing (2.1) from Proposition 2.1 with (4.4) from Theorem 4.1. This
yields

$C_{r,1}^{\mathbb{C}}\leq C_{r}$

for all $r\in[2,\infty]$. Putting together these inequalities we obtain the
announced optimal estimates:

$C_{r}=C_{1,r}^{\mathbb{C}}=C_{r,1}^{\mathbb{C}},$

for all $r\in[2,\infty]$. ∎

## References

  * [1] N. Albuquerque, F. Bayart, D. Pellegrino and J. Seoane-Sepúlveda, Sharp generalizations of the Bohnenblust–Hille inequality, J. Funct. Analysis, 266 (2014), 3726–3740.
  * [2] S. Arunachalam, A. Dutt, F. Escudero Gutiérrez and C. Palazuelos, Learning low-degree quantum objects. arXiv preprint arXiv:2405.10933, (2024).
  * [3] F. Bayart, Multiple summing maps: coordinatewise summability, inclusion theorems and p-Sidon sets. J. Funct. Anal. 274 (2018), no. 4, 1129–1154.
  * [4] F. Bayart, D. Pellegrino and J. B. Seoane-Sepúlveda, The Bohr radius of the $n$-dimensional polydisk is equivalent to $\sqrt{(\log n)/n}$, Adv. Math. 264 (2014), 726–746.
  * [5] A. Belacel, A. Bougoutaia, R. Macedo and P. Rueda, Intermediate classes of nuclear multilinear operators, Bull. Braz. Math. Soc. (N.S.) 54 (2023),https://doi.org/10.1007/s00574-023-00365-5
  * [6] R. Blei, Analysis in Integer and Fractional Dimensions. Cambridge Studies in Advanced Mathematics, 71. Cambridge University Press, Cambridge, 2001. xx+556 pp.
  * [7] G. Botelho, D. Freitas, Summing multilinear operators by blocks: The isotropic and anisotropic cases. J. Math. Anal. Appl. 490 (2020), no. 1, 124203, 21 pp.
  * [8] W.V. Cavalcante, D. Núñez-Alarcón, D.M. Pellegrino and P. Rueda, Optimal constants of the mixed Littlewood inequalities: the complex case. Math. Inequal. Appl. 25, no. 1 (2022), 205–220.
  * [9] J. Diestel, H. Jarchow, A. Tonge, Absolutely summing operators. Cambridge Studies in Advanced Mathematics, 43. Cambridge University Press, Cambridge, 1995. xvi+474 pp.
  * [10] D. Diniz, G. A. Muñoz-Fernández, D. Pellegrino and J. B. Seoane-Sepúlveda, Lower Bounds for the constants in the Bohnenblust-Hille inequality: the case of real scalars, Proc. Amer. Math. Soc. 142 (2014), n. 2, 575–580.
  * [11] J.E. Littlewood, On bounded bilinear forms in an infinite number of variables, Q. J. Math. Oxford 1 (1930) 164–174.
  * [12] A. Montanaro, Some applications of hypercontractive inequalities in quantum information theory. J. Math. Phys. 53 (2012), no. 12, 122206, 15 pp.
  * [13] D. Núñez-Alarcón, J. Santos, D. Serrano-Rodríguez, Unified Grothendieck’s and Kwapień’s Theorems for Multilinear Operators. Bull Braz Math Soc, New Series 55, 3 (2024).
  * [14] D. Núñez-Alarcón, D. Serrano-Rodríguez and K. Teixeira, Sharp exponents for anisotropic Hardy–Littlewood type of inequalities, Bull Braz Math Soc, To appear (2024).
  * [15] D. Pellegrino, D. Santos and J. Santos, Optimal blow up rate for the constants of Khinchin type inequalities, Quaest. Math. 41, (2018) doi:10.2989/16073606.2017.1380724
  * [16] D. Pellegrino, J. Santos, J. Seoane-Sepulveda, Some techniques on nonlinear analysis and applications. Adv. Math. 229 (2012), no. 2, 1235–1265.
  * [17] D. Pellegrino ,J. Santos, D. Serrano and E. Teixeira, A regularity principle in sequence spaces and applications, Bull. Sci. math. 141, (2017), doi:10.1016/j.bulsci.2017.09.001
  * [18] A. Raposo Jr, D. Serrano-Rodríguez, Coefficients of multilinear forms on sequence spaces, Bull Braz Math Soc, New Series 54, 43 (2023).
  * [19] O. Ramaré, An Explicit Croot-Łaba-Sisask Lemma Free of Probabilistic Language, Bull Braz Math Soc, New Series 55, 23 (2024).
  * [20] J. Slote, A. Volberg, and H. Zhang, Noncommutative Bohnenblust–Hille inequality in the Heisenberg–Weyl and Gell-Mann bases with applications to fast learning. arXiv preprint arXiv:2301.01438, (2023).


# Memory Augmented Large Language Models are Computationally Universal

Dale Schuurmans
Google Brain & University of Alberta

###### Abstract

We show that transformer-based large language models are computationally
universal when augmented with an external memory. Any deterministic language
model that conditions on strings of bounded length is equivalent to a finite
automaton, hence computationally limited. However, augmenting such models with
a read-write memory creates the possibility of processing arbitrarily large
inputs and, potentially, simulating any algorithm. We establish that an
existing large language model, Flan-U-PaLM 540B, can be combined with an
associative read-write memory to exactly simulate the execution of a universal
Turing machine, $U_{15,2}$. A key aspect of the finding is that it does not
require any modification of the language model weights. Instead, the
construction relies solely on designing a form of stored instruction computer
that can subsequently be programmed with a specific set of prompts.

##  1 Introduction

Interest in large language models has grown dramatically since the early
successes of GPT-2, GPT-3 and InstructGPT [Radford et al., 2019, Brown et al.,
2020, Ouyang et al., 2022], and more recently with the popularity of ChatGPT
[Schulman et al., 2022]. Beyond simple question answering, where an input
string posing a question might elicit an output string containing a reasonable
answer, an important discovery has been the emergence of _in-context learning_
, where prepending a question with a set of related (question, answer) pairs
significantly improves question answering accuracy [Radford et al., 2019].
Even adding a natural language instruction before example pairs appears to
further enhance language model capabilities [Brown et al., 2020]. More
recently, _chain of thought prompting_ has been found to improve question
answering ability in scenarios where multiple reasoning steps are required to
arrive at a final answer, such as answering math word problems [Wei et al.,
2022b].

Despite these results, current transformer-based large language models remain
fundamentally limited as they can only condition on an input string of bounded
length, such as 4096 tokens. This makes such models formally equivalent to
finite automata, hence restricted in the computations they can express.
However, recent works have begun to investigate techniques for chaining
multiple calls to a language model by processing model outputs then passing
these back as subsequent inputs to the model. An example is _least to most
prompting_ , where a complex reasoning question is answered first by prompting
the model to produce simpler sub-questions, then passing each sub-question and
resulting answer back into the model to help answer subsequent sub-questions,
until a final answer is reached [Zhou et al., 2022]. Another example is work
on _language model cascades_ that investigates various strategies for
processing model outputs and feeding these as inputs to subsequent language
model calls [Dohan et al., 2022]. Such works raise the question of whether
augmenting a language model with an external feedback loop is merely useful,
or fundamentally expands the range of computations that can be performed. To
investigate this question, we consider augmenting a language model with an
external read-write memory and ask whether this confers the ability to
simulate any algorithm on any input.

This paper gives an affirmative answer by establishing computational
universality for a specific large language model, Flan-U-PaLM 540B [Chung et
al., 2022], augmented with an associative read-write memory. A key aspect of
the result is that it is achieved by developing a simple form of _stored
instruction computer_ [von Neumann, 1945] that connects the language model to
an associative memory, then follows a simple instruction cycle where the next
input prompt to be passed to the language model is retrieved from memory, the
output of the language model is parsed to recover any variable assignments
that are then stored in the associative memory, and the next instruction is
retrieved (i.e., the next input prompt to be provided to the language model).
Each parsing step between the language model and memory is performed by a
simple regular expression match (i.e., a finite automaton).

Once a stored instruction computer has been created, a specific “prompt
program” is designed to drive the system to simulate a universal Turing
machine $U_{15,2}$ [Neary, 2008, Neary and Woods, 2009]. Proving the fidelity
of the simulation reduces to checking a finite set of prompt-result behaviours
and verifying that the language model produces the correct output for each of
the finite set of possible input prompt strings it might encounter. That is,
although the overall input-output behaviour of the Flan-U-PaLM 540B model is
not fully understood, a sufficiently reliable subset of its input-output map
can be isolated and controlled to simulate a universal computer. Importantly,
this result does not involve any additional “training” of the language model
(i.e., no modification of its pre-trained weights), but instead relies solely
on providing specific prompt strings to the model and parsing its outputs to
determine values to be saved in memory.

##  2 Stored instruction computer

As noted, there are many ways to orchestrate feedback between the outputs of a
language model and subsequent input prompts [Zhou et al., 2022, Dohan et al.,
2022]. In developing a simple feedback loop we would like to minimize external
processing and perform as much of the computation with the language model as
possible, while still supporting computational universality. To achieve this,
we consider a simple form of _stored instruction computer_ [von Neumann,
1945], where the language model plays the role of a central processing unit
(CPU), and the random access memory (RAM) is supplied by an external
associative memory. Such an architecture allows for a simple interaction loop
that can support general computation and convenient programmability. In this
architecture, the external associative memory is a simple “dictionary”,
MEMORY, that maps unique keys to values, or equivalently, maps variable names
to values, or address locations to values. Unlike the RAM in a physical
computer, variable names will be strings (i.e., finite length sequences of
symbols from a finite alphabet) to support convenient interaction with a
language model, while values will be strings or integers.

To ensure that computational universality does not follow simply from external
processing capability, all interaction between the language model and the
memory will be restricted to _finite state computation_ , such as simple
regular expression parsers.

All code below will be given in Python 3 using the standard regular expression
library re. Note that the regular expressions used for pre and post processing
are rudimentary and can easily be improved in several ways; the versions given
are merely sufficient to establish the main points in this paper.

###  2.1 Post processing language model outputs

The output string from the language model will be parsed by a simple regular
expression that detects assignments in the form variable_name = "value", which
are then applied to the associative memory as MEMORY[variable_name] = "value".
The variable assignment function assignments is shown below.

    def assignments(string):
      global MEMORY
      regex = ’(?s)(?:((?:\w|\-)+)\s*=\s*(?:\"((?:.*\n)|(?:[^\"]*))\"))(.*)’
      matches = re.findall(regex, string)
      suffix = ’’
      while len(matches) > 0:
        label, value, suffix = matches[0]
        MEMORY[label] = value
        matches = re.findall(regex, suffix)
      return suffix

Additionally, splicing is allowed in value strings before being assigned to
memory; that is, we include a regular expression parser that detects
occurrences of the pattern %[variable_name] in any value string, replacing any
such occurrence with the string at memory location variable_name, i.e.,
MEMORY[variable_name], before assignment. The substitution function substitute
is shown below.

    def substitute(string, char):
      global MEMORY, BLANK
      regex = f"(?s)(.*?)(?:{char}\[(\w+)\])(.*)"
      matches = re.findall(regex, string)
      string = suffix = ’’
      while len(matches) > 0:
        prefix, label, suffix = matches[0]
        if label not in MEMORY:
          MEMORY[label] = BLANK # new label has BLANK value by default
        string += prefix + str(MEMORY[label])
        matches = re.findall(regex, suffix)
      string += suffix
      return string

As a final convenience, we also allow integer values to be stored and
incremented or decremented. Such integer variable updating is achieved by
parsing the output string for occurrences of the pattern variable_name +=
increment or variable_name -= decrement then applying the updates to
variable_name in memory. Importantly, integer addition is also a finite state
operation (see, for example, [Sipser, 2013, Problem 1.32]), while the Python
standard implements the bignum type that handles arbitrarily large integers.
The update function updates is shown below.

    def updates(string):
      global MEMORY
      regex = ’(\w+)\s*((?:\+|\-)=)\s*(\d+)’
      matches = re.findall(regex, string)
      if matches != None:
        for match in matches:
          label, operator, valuestring = match
          sign = 1 if operator == "+=" else -1
          value = int(valuestring) * sign
          if label in MEMORY and isinstance(MEMORY[label], int):
            MEMORY[label] += value
          else:
            MEMORY[label] = value # new or non-int starts from 0 by default

###  2.2 Pre processing language model inputs

Each input prompt to the language model will be retrieved from a special
memory location op and passed as a prompt to the language model in each
computational cycle; that is, MEMORY[’op’] will serve as an “instruction
register”. Instruction branching can then be achieved simply by assigning a
different prompt string to MEMORY[’op’] during a computational cycle.

To access stored memory values, we also allow splicing in the input prompt
string retrieved from op. In particular, the regular expression parser for the
input prompt first detects patterns of the form @[variable_name] and replaces
these by splicing in the string retrieved from MEMORY[variable_name] before
passing the prompt string to the language model. For input pre processing, it
will also be convenient to allow repeated substitutions of nested @
occurrences, so we add the repeated substitution function substitute_nested
below. Note that, technically, allowing arbitrarily nested substitutions can
simulate a context free grammar [Sipser, 2013], which violates the constraint
of finite state computation; however, we will only use bounded depth nesting
(depth bound 2) below to ensure the pre and post processing steps all remain
achievable by finite state computation.

    def substitute_nested(string, char):
      regex = f"(?s)(.*?)(?:{char}\[(\w+)\])(.*)"
      while re.match(regex, string) != None:
        string = substitute(string, char)
      return string

###  2.3 Compute cycle

Finally, a stored instruction computer can run a single compute cycle:
retrieve the next prompt string from MEMORY[’op’]; process the prompt string
by possibly splicing in other strings from memory; pass the prompt string to
the language model; process the output string, possibly splicing in other
strings from memory, detecting all assignments and increment/decrement
updates, applying these to memory; and repeat. Computation proceeds until the
next instruction in MEMORY[’op’] is the special instruction string ’halt’. In
particular, the main loop is constructed as follows.

    def main():
      global MEMORY
      while True:
        op = MEMORY[’op’]
        if op == ’halt’:
          return None
        prompt = substitute_nested(op, ’@’)
        result = call_llm_server(prompt)
        result = substitute(result, ’%’)
        suffix = assignments(result)
        updates(suffix)

This main instruction loop demonstrates how the language model plays the role
of the CPU, effectively taking the next instruction and its operands expressed
by the prompt string and acting on these to produce the result string, which
is then used to update the memory.

##  3 Universal Turing machine

The concept of a universal computer—a computing machine that can simulate the
execution of any other computing machine on any input—was developed by Alan
Turing to solve the _Entscheidungsproblem_ [Turing, 1937]. By the Church-
Turing thesis, all computational mechanisms are considered to be expressible
by a _Turing machine_ , which informally consists of a finite state controller
and an unboundedly large “tape” memory with a “head” that can access a single
tape location and move one location left or right in each compute cycle
[Sipser, 2013, Chapter 3].

Formally, a Turing machine consists of a tuple ${\cal
M}=(Q,\Sigma,b,q_{0},T,f)$, where $Q$ is a finite set of states, $\Sigma$ is a
finite set of tape symbols, $b\in\Sigma$ is the blank symbol, $q_{0}\in Q$ is
the start state, $T\subseteq Q\times\Sigma$ is the set of halting (state,
symbol) pairs, and $f:Q\times\Sigma\rightarrow\Sigma\times\\{-1,+1\\}\times Q$
is a finite set of transition rules that specify the operation of the machine
in each compute cycle. We assume the tape is bi-directionally unbounded, so
memory locations can be indexed by an integer $i\in\mathbb{Z}$. Let
$i_{0}\in\mathbb{Z}$ denote the initial location of the tape head.

The execution of a Turing machine can then be defined as follows. The tape
memory is initialized with a finite number of non-blank symbols with all other
locations blank, $\cal M$ starts in state $q_{0}$, and the tape head starts at
location $i_{0}$. At the start of each compute cycle, the tape head is at some
location $i\in\mathbb{Z}$, the machine is in some state $q\in Q$, and some
symbol $\sigma\in\Sigma$ is under the tape head. This combination determines
the update $f(q,\sigma)\mapsto(\sigma^{\prime},m,q^{\prime})$, specifying that
the symbol $\sigma^{\prime}$ is written at the current memory location $i$,
the machine state $q$ is updated to $q^{\prime}$, and the tape head is moved
one step left, to location $i^{\prime}=i-1$ if $m=-1$, otherwise one step
right, to location $i^{\prime}=i+1$ if $m=+1$. The compute cycle repeats until
the machine encounters a configuration $(q,\sigma)\in T$. Non-halting
computations are possible.

[Shannon, 1956] began an effort to identify the smallest universal Turing
machines in terms of the number of states and tape symbols used. A gap remains
between the known upper and lower bounds on the state and symbol counts for a
universal Turing machine [Neary, 2008, Neary and Woods, 2009], but
progressively smaller universal Turing machines have been identified. We will
consider one such machine in this paper, $U_{15,2}$, which uses only 15 states
and 2 tape symbols [Neary and Woods, 2009]. This Turing machine is Pareto
optimal in terms of the smallest known universal Turing machines [Neary,
2008]. Formally, the Turing machine $U_{15,2}$ can be defined by a tuple
$(Q,\Sigma,b,q_{0},T,f)$, where $Q=\\{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O\\}$,
$\Sigma=\\{0,1\\}$, $b=0$, $q_{0}=A$, $T=\\{(J,1)\\}$, and the transition
function $f$ is defined in Table 1. The initial head position $i_{0}$ depends
on how the memory is initialized for a given problem instance.

| $A$ | $B$ | $C$ | $D$ | $E$ | $F$ | $G$ | $H$
---|---|---|---|---|---|---|---|---
$0$ | $0,+,B$ | $1,+,C$ | $0,-,G$ | $0,-,F$ | $1,+,A$ | $1,-,D$ | $0,+,H$ | $1,-,I$
$1$ | $1,+,A$ | $1,+,A$ | $0,-,E$ | $1,-,E$ | $1,-,D$ | $1,-,D$ | $1,-,G$ | $1,-,G$

| $I$ | $J$ | $K$ | $L$ | $M$ | $N$ | $O$
---|---|---|---|---|---|---|---
$0$ | $0,+,A$ | $1,-,K$ | $0,+,L$ | $0,+,M$ | $0,-,B$ | $0,-,C$ | $0,+,N$
$1$ | $1,-,J$ | halt | $1,+,N$ | $1,+,L$ | $1,+,L$ | $0,+,O$ | $1,+,N$

Table 1:  Transition table for the universal Turing machine $U_{15,2}$. Rows
are indexed by the read symbol $\sigma$, columns are indexed by the state $q$,
and each table entry $(\sigma^{\prime},m,q^{\prime})$ specifies the write
symbol $\sigma^{\prime}$, the tape head move $m\in\\{-1,+1\\}$, and the next
state $q^{\prime}$.

##  4 Simulating $U_{15,2}$ with a prompt program

In this section, we show that the stored instruction computer defined in
Section 2 can be programmed to simulate the universal Turing machine
$U_{15,2}$, provided that a finite set of conditional assignments and
evaluations can be correctly performed by the language model. That is, we
first propose a specific prompt program that, if executed correctly, exactly
simulates $U_{15,2}$. The next section will then verify that a specific large
language model, Flan-U-PaLM 540B, is indeed able to execute each of the
program instructions correctly.

A prompt program consists of a finite set of pre designed strings stored in
memory that provide input prompts to the language model as part of the main
compute cycle, via a call to main() outlined in Section 2. To mimic the
behaviour of $U_{15,2}$, we design the prompt program as follows. First, a
“boot” prompt is designed that “instructs” the language model about the
behaviour of variable assignments, variable evaluations after assignment, and
if-then conditionals.

    boot = """
    result = " op="%[B]" %[i]="0" i+=1 "
    if 0==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    " op="%[B]" %[i]="0" i+=1 "

    result = " op="%[B]" %[i]="0" i+=1 "
    if 1==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    " op="%[A]" %[i]="1" i+=1 "

    result = " op="%[C]" %[i]="1" i+=1 "
    if 0==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    " op="%[C]" %[i]="1" i+=1 "

    result = " op="%[C]" %[i]="1" i+=1 "
    if 1==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    " op="%[A]" %[i]="1" i+=1 "

    result = " op="%[G]" %[i]="0" i-=1 "
    if 0==1 then result = " op="%[E]" %[i]="0" i-=1 "
    $result
    " op="%[G]" %[i]="0" i-=1 "

    result = " op="%[G]" %[i]="0" i-=1 "
    if 1==1 then result = " op="%[E]" %[i]="0" i-=1 "
    $result
    " op="%[E]" %[i]="0" i-=1 "

    result = " op="%[F]" %[i]="0" i-=1 "
    if 0==1 then result = " op="%[E]" %[i]="1" i-=1 "
    $result
    " op="%[F]" %[i]="0" i-=1 "

    result = " op="%[F]" %[i]="0" i-=1 "
    if 1==1 then result = " op="%[E]" %[i]="1" i-=1 "
    $result
    " op="%[E]" %[i]="1" i-=1 "

    result = " op="%[K]" %[i]="1" i-=1 "
    if 0==1 then result = " op="halt" "
    $result
    " op="%[K]" %[i]="1" i-=1 "

    result = " op="%[K]" %[i]="1" i-=1 "
    if 1==1 then result = " op="halt" "
    $result
    " op="halt" "

    result = " op="%[L]" %[i]="0" i+=1 "
    if 0==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result
    " op="%[L]" %[i]="0" i+=1 "

    result = " op="%[L]" %[i]="0" i+=1 "
    if 1==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result
    " op="%[N]" %[i]="1" i+=1 "

    result = " op="%[C]" %[i]="0" i-=1 "
    if 1==1 then result = " op="%[O]" %[i]="0" i+=1 "
    $result
    " op="%[O]" %[i]="0" i+=1 "

    """

Next, a series of “instruction” prompts are defined. Each of these strings is
intended to express the logic of a corresponding Turing machine state in
$U_{15,2}$ specified in Table 1.

    A = """@[boot]result = " op="%[B]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    """
    B = """@[boot]result = " op="%[C]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result
    """
    C = """@[boot]result = " op="%[G]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="0" i-=1 "
    $result
    """
    D = """@[boot]result = " op="%[F]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="1" i-=1 "
    $result
    """
    E = """@[boot]result = " op="%[A]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[D]" %[i]="1" i-=1 "
    $result
    """
    F = """@[boot]result = " op="%[D]" %[i]="1" i-=1 "
    $result
    """
    G = """@[boot]result = " op="%[H]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result
    """
    H = """@[boot]result = " op="%[I]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result
    """
    I = """@[boot]result = " op="%[A]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[J]" %[i]="1" i-=1 "
    $result
    """
    J = """@[boot]result = " op="%[K]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="halt" "
    $result
    """
    K = """@[boot]result = " op="%[L]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result
    """
    L = """@[boot]result = " op="%[M]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result
    """
    M = """@[boot]result = " op="%[B]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result
    """
    N = """@[boot]result = " op="%[C]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[O]" %[i]="0" i+=1 "
    $result
    """
    O = """@[boot]result = " op="%[N]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result
    """

It helps to understand how this prompt program is intended to work. First,
note that the memory location ’i’ is intended to keep track of the current
location of the Turing machine head, so that any update i-=1 will correspond
to moving the head one step left, and i+=1 will correspond to moving the head
one step right. Next, consider the post processing of one of the result
strings, for example " op=%[N]" %[i]="1" i+=1 ". In this string, the
expression %[i]="1" is intended to write the target symbol ’1’ to the memory
location indexed by MEMORY[’i’]. That is, during post processing, any
substring of the form %[x] will first be replaced by the string in MEMORY[’x’]
before performing any assignments, as explained in Section 2. Thus, given
%[i]="1" the substring %[i] will first be replaced by the value in
MEMORY[’i’], say $\ell$, which then serves as the label in memory to be
assigned the value ’1’. For example, if we assume MEMORY[’i’] = 42 and
MEMORY[’42’] = ’0’, then after post processing and assignment we will have
MEMORY[’42’] = ’1’. Control branching, i.e., a state transition, is achieved
by assigning a new instruction string from {A, …, O} to the instruction
register MEMORY[’op’], as specified by the assignment string op="%[N] in the
example.

In the pre processing phase, the prompt string is obtained from MEMORY[’op’],
then substrings of the form @[x] are replaced by the string stored in
MEMORY[’x’]. This allows for more compact instruction strings A, …, O, since
the lengthy boot string can just be spliced in during pre processing. More
importantly, the symbol at the current head position can be read with @[@[i]].
To see why this works, note that the preprocessor will apply _nested_
substitutions of the @[x] patterns, as discussed in Section 2. Therefore, if
we continue to assume that MEMORY[’i’] = 42 and MEMORY[’42’] = ’1’, the first
substitution of @[@[i]] will result in @[’42’], and the second substitution
will result in ’1’. That is, after pre processing, the substring @[@[i]] is
replaced with the value found in MEMORY[MEMORY[’i’]], i.e., the symbol at the
current position of the tape head, which in this case will be ’1’.

Given this understanding, it is easy to verify that each of the instruction
strings A, …, O correctly mimics the logic of the corresponding states $A$, …,
$O$ in Table 1, including conditioning on the current symbol in the head
position, writing the correct symbol to the current head position, moving the
head position in the correct direction, and updating the state by assigning
the correct next instruction to ’op’.

Finally, to simulate the behaviour of $U_{15,2}$, we also have to consider the
initial contents of the tape memory. Let the variable TAPE be assigned to a
string that covers the non-blank portion of the initial memory for $U_{15,2}$,
which must be finitely long by definition. Also let i$=i_{0}$ contain the
initial position of the tape head. To simulate the Turing machine from this
configuration, we first initialize the associative memory, MEMORY, as follows,
then simply call main() as specified in Section 2.

    MEMORY = {’boot’:boot}
    for s in ’ABCDEFGHIJKLMNO’:
      MEMORY[s] = eval(s)
    for loc in range(len(TAPE)):
      MEMORY[str(loc)] = TAPE[loc]
    BLANK = ’0’
    MEMORY[’i’] = i
    MEMORY[’op’] = A
    main()

We now claim that each compute cycle of main() maintains an exact equivalence
with each compute cycle of the Turing machine $U_{15,2}$. The proof is by
induction on the number of compute cycles.

At initialization, there is an equivalence between: the contents of the Turing
machine memory tape and the contents of MEMORY labelled by location numbers
(with all unassigned locations assumed to be blank); the initial tape head
location $i_{0}$ and i; the initial state $A$ and initial instruction A.

Then, inductively, assume the same equivalence holds at the onset of a compute
cycle. The Turing machine will then be updated according to
$(q,\sigma)\mapsto(\sigma^{\prime},m,q^{\prime})$ following the specification
in Table 1. Now assume the corresponding prompt string after pre processing
with the same current symbol in MEMORY[MEMORY[’i’]] (i.e., the current
location of the simulated tape head) returns the correct result string after
the call to call_llm_server(prompt). Then one can verify, on a case by case
basis for each (state, symbol) pair, that the result string specifies the same
symbol to be written to the current head location, specifies the same
direction to move the head, and specifies the corresponding next instruction,
thus the equivalence is maintained at the end of the cycle.

To illustrate one of the (state, symbol) verifications, consider the first
entry in Table 1, which specifies the Turing machine update
$(A,0)\mapsto(0,+,B)$. Observe that the instruction A pre processed with the
same input symbol ’0’ at MEMORY[MEMORY[’i’]] will return the result string "
op=%[B]" %[i]="0" i+=1 " assuming the language model operates correctly
(verified below). In this case, the post processing phase will write the
corresponding symbol ’0’ to the current memory location, move the head right
+=1, and assign B to be the next instruction, thus maintaining the
equivalence.

Similarly, if the current input is $1$, the Turing machine update is
$(A,1)\mapsto(1,+,A)$. In this case, observe that if the instruction A pre
processed with the same input symbol ’1’ at MEMORY[MEMORY[’i’]], the condition
will be true and the result string will be " op=%[A]" %[i]="1" i+=1 " assuming
the language model operates correctly. Post processing will once again
maintain the equivalence.

A similar verification succeeds for all 29 (state, symbol) cases. (Note that
the update in state $F$ does not depend on the input, so there is one fewer
case than the total number of (state, symbol) pairs.)

It remains only to verify that a language model can produce the correct result
string given any of the instruction strings after pre processing with the
current memory symbol.

##  5 Verifying correct execution using Flan-U-PaLM 540B

We now consider the specific language model Flan-U-PaLM 540B [Chung et al.,
2022], which is a large 540B parameter model that has been refined with
additional instruction fine-tuning. To ensure deterministic computation, the
decoding temperature for the language model is set to zero (pure greedy
decoding).

To complete the argument, we now simply enumerate each of the possible (state,
symbol) combinations and verify that the language model produces the correct
result string given an input prompt string composed from the corresponding
instruction and pre processed with the corresponding input symbol. This is
simply a brute force proof, calling the language model with each possible
input prompt and verifying that the correct result string is indeed returned.
There are 29 cases. (So, yeah, human readable but not human enjoyable,
apologies.)

Verification test 1 (state A read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = A
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 1

    @[boot]result = " op="%[B]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result

    " op="%[B]" %[i]="0" i+=1 "

Verification test 2 (state A read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = A
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 2

    @[boot]result = " op="%[B]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result

    " op="%[A]" %[i]="1" i+=1 "

Verification test 3 (state B read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = B
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 3

    @[boot]result = " op="%[C]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result

    " op="%[C]" %[i]="1" i+=1 "

Verification test 4 (state B read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = B
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 4

    @[boot]result = " op="%[C]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[A]" %[i]="1" i+=1 "
    $result

    " op="%[A]" %[i]="1" i+=1 "

Verification test 5 (state C read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = C
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 5

    @[boot]result = " op="%[G]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="0" i-=1 "
    $result

    " op="%[G]" %[i]="0" i-=1 "

Verification test 6 (state C read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = C
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 6

    @[boot]result = " op="%[G]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="0" i-=1 "
    $result

    " op="%[E]" %[i]="0" i-=1 "

Verification test 7 (state D read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = D
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 7

    @[boot]result = " op="%[F]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="1" i-=1 "
    $result

    " op="%[F]" %[i]="0" i-=1 "

Verification test 8 (state D read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = D
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 8

    @[boot]result = " op="%[F]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[E]" %[i]="1" i-=1 "
    $result

    " op="%[E]" %[i]="1" i-=1 "

Verification test 9 (state E read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = E
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 9

    @[boot]result = " op="%[A]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[D]" %[i]="1" i-=1 "
    $result

    " op="%[A]" %[i]="1" i+=1 "

Verification test 10 (state E read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = E
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 10

    @[boot]result = " op="%[A]" %[i]="1" i+=1 "
    if @[@[i]]==1 then result = " op="%[D]" %[i]="1" i-=1 "
    $result

    " op="%[D]" %[i]="1" i-=1 "

Verification test 11 (state F read 0 == state F read 1)

    op = F
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 11

    @[boot]result = " op="%[D]" %[i]="1" i-=1 "
    $result

    op="%[D]" %[i]="1" i-=1

Verification test 12 (state G read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = G
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 12

    @[boot]result = " op="%[H]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result

    " op="%[H]" %[i]="0" i-=1 "

Verification test 13 (state G read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = G
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 13

    @[boot]result = " op="%[H]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result

    " op="%[G]" %[i]="1" i-=1 "

Verification test 14 (state H read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = H
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 14

    @[boot]result = " op="%[I]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result

    " op="%[I]" %[i]="1" i-=1 "

Verification test 15 (state H read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = H
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 15

    @[boot]result = " op="%[I]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="%[G]" %[i]="1" i-=1 "
    $result

    " op="%[G]" %[i]="1" i-=1 "

Verification test 16 (state I read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = I
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 16

    @[boot]result = " op="%[A]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[J]" %[i]="1" i-=1 "
    $result

    " op="%[A]" %[i]="0" i+=1 "

Verification test 17 (state I read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = I
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 17

    @[boot]result = " op="%[A]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[J]" %[i]="1" i-=1 "
    $result

    " op="%[J]" %[i]="1" i-=1 "

Verification test 18 (state J read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = J
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 18

    @[boot]result = " op="%[K]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="halt" "
    $result

    " op="%[K]" %[i]="1" i-=1 "

Verification test 19 (state J read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = J
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 19

    @[boot]result = " op="%[K]" %[i]="1" i-=1 "
    if @[@[i]]==1 then result = " op="halt" "
    $result

    " op="halt" "

Verification test 20 (state K read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = K
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 20

    @[boot]result = " op="%[L]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result

    " op="%[L]" %[i]="0" i+=1 "

Verification test 21 (state K read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = K
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 21

    @[boot]result = " op="%[L]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result

    " op="%[N]" %[i]="1" i+=1 "

Verification test 22 (state L read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = L
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 22

    @[boot]result = " op="%[M]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result

    " op="%[M]" %[i]="0" i+=1 "

Verification test 23 (state L read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = L
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 23

    @[boot]result = " op="%[M]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result

    " op="%[L]" %[i]="1" i+=1 "

Verification test 24 (state M read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = M
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 24

    @[boot]result = " op="%[B]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result

    " op="%[B]" %[i]="0" i-=1 "

Verification test 25 (state M read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = M
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 25

    @[boot]result = " op="%[B]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[L]" %[i]="1" i+=1 "
    $result

    " op="%[L]" %[i]="1" i+=1 "

Verification test 26 (state N read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = N
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 26

    @[boot]result = " op="%[C]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[O]" %[i]="0" i+=1 "
    $result

    " op="%[C]" %[i]="0" i-=1 "

Verification test 27 (state N read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = N
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 27

    @[boot]result = " op="%[C]" %[i]="0" i-=1 "
    if @[@[i]]==1 then result = " op="%[O]" %[i]="0" i+=1 "
    $result

    " op="%[O]" %[i]="0" i+=1 "

Verification test 28 (state O read 0)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’0’
    op = O
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 28

    @[boot]result = " op="%[N]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result

    " op="%[N]" %[i]="0" i+=1 "

Verification test 29 (state O read 1)

    head = MEMORY[’i’]
    MEMORY[str(head)] = ’1’
    op = O
    prompt = substitute_nested(op, ’@’)
    result = call_llm_server(prompt)
    print(op)
    print(result)

Output 29

    @[boot]result = " op="%[N]" %[i]="0" i+=1 "
    if @[@[i]]==1 then result = " op="%[N]" %[i]="1" i+=1 "
    $result

    " op="%[N]" %[i]="1" i+=1 "

This completes the proof.

##  6 Discussion

Hopefully the reader has been convinced by this point. There are some
reflections on this study that are useful to share.

Although the verification of computational universality is straightforward,
the language model’s behaviour was brittle. Success was not achieved with
every large language model considered, and effort was required to engineer the
prompts. For example, the instruction strings A, …, O with the substitution
symbols @ and % are terse and not particularly elegant for humans to read, yet
compactness seemed essential to get the language model to produce correct
results. Eliciting correct evaluations of variable assignments was sometimes a
challenge, but by far the biggest challenge was getting the language model to
interpret conditionals properly. The reader might notice that the conditionals
have been reduced to if-then rather than if-then-else forms. This was not an
accident: I was not able to get the language model to reliably produce correct
outputs for if-then-else conditionals. The difficulty with conditionals also
makes it challenging to simulate other, smaller universal Turing machines,
such as $U_{6,4}$ [Neary and Woods, 2009], since this requires a series of 3
conditionals for each state, which I could not get to work without introducing
phantom states and reducing instructions to only a single conditional,
ultimately ending up with a far less digestible construction. Presumably
improvements in the underlying language models will mitigate such challenges.

Earlier versions of this work considered simulating Rule 110 for a one
dimensional cellular automaton [Wolfram, 2002], leveraging the fact that this
is known to be a (weakly) Turing complete [Cook, 2004]. Although far more
visually appealing, Rule 110 requires an unbounded periodic initialization to
an simulate arbitrary Turing machine, and ultimately the more direct
simulation of $U_{15,2}$ presented in this paper, which requires only a
bounded initialization, appears to be more convincing.

There is an interesting analogy to the “programming language” developed in
Sections 2 and 4 and some of the earliest programming languages [Böhm, 1954],
including the first assembly languages [Booth and Britten, 1947]. The latter
is particularly reminiscent given the reliance on human readable labels for
branch control. It is interesting to speculate about what other concepts in
the history of software engineering (e.g., high level languages, modularity,
libraries, etc.) might be useful for eliciting desired computational behaviour
from a large language model.

The result in this paper is distinct from previous studies that investigate
the computational universality of neural sequence models, such as recurrent
neural networks
[Siegelmann and Sontag, 2019, Weiss et al., 2018] and Transformers [Pérez et
al., 2019],
[Bhattamishra et al., 2020, Wei et al., 2022a]. The key distinction is that we
consider a _fixed_ language model with frozen weights, and show how external
memory augmentation can elicit universal computational behaviour. By contrast
these past studies have shown how computationally universal behaviour can be
recovered by _manipulating_ the weights of the neural network, typically using
unbounded (or sufficiently high) precision weights to encode data structures,
like multiple stacks. An advantage of these past works is that they do not
require any external memory to demonstrate universal computational behaviour.
On the other hand, these results do not apply to existing large language
models without altering their weights (as far as currently known). The results
in this paper show that large language models are already computationally
universal—as they exist currently—provided only that they have access to an
unbounded external memory.

## Acknowledgments

Sincere thanks to Noah Fiedel, Ramki Gummadi, András György, Chris Harris,
Tengyu Ma, Jason Wei, Sherry Yang, Denny Zhou and Martin Zinkevich for
essential discussions leading to this work. Thanks also to Google Brain and my
team members for providing an ideal environment for conducting exploratory
research. Support from the CIFAR Canada AI Research Chairs program, NSERC, and
Amii is also gratefully acknowledged.

## References

  * [Bhattamishra et al., 2020] Bhattamishra, S., Patel, A., and Goyal, N. (2020).  On the computational power of Transformers and its implications in sequence modeling.  In Conference on Computational Natural Language Learning (CONLL).
  * [Böhm, 1954] Böhm, C. (1954).  Calculatrices digitales du déchiffrage de formules logico-mathématiques par la machine même dans la conception du programme.  PhD thesis, ETH Zürich.
  * [Booth and Britten, 1947] Booth, A. and Britten, K. (1947).  General considerations in the deisgn of an all purpose electronic digital computer.  Technical report, Institute for Advanced Study, Princeton.  2nd ed.
  * [Brown et al., 2020] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. (2020).  Language models are few-shot learners.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Chung et al., 2022] Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., Webson, A., Gu, S. S., Dai, Z., Suzgun, M., Chen, X., Chowdhery, A., Castro-Ros, A., Pellat, M., Robinson, K., Valter, D., Narang, S., Mishra, G., Yu, A., Zhao, V., Huang, Y., Dai, A., Yu, H., Petrov, S., Chi, E., Dean, J., Devlin, J., Roberts, A., Zhou, D., Le, Q., and Wei, J. (2022).  Scaling instruction-finetuned language models.  arXiv 2210.11416.
  * [Cook, 2004] Cook, M. (2004).  Universality in elementary cellular automata.  Complex Systems, 15:1–40.
  * [Dohan et al., 2022] Dohan, D., Xu, W., Lewkowycz, A., Austin, J., Bieber, D., Lopes, R. G., Wu, Y., Michalewski, H., Saurous, R. A., Sohl-dickstein, J., Murphy, K., and Sutton, C. (2022).  Language model cascades.  arXiv 2207.10342.
  * [Neary, 2008] Neary, T. (2008).  Small universal Turing machines.  PhD thesis, National University of Ireland, Maynooth.
  * [Neary and Woods, 2009] Neary, T. and Woods, D. (2009).  Four small universal Turing machines.  Fundamenta Informaticae, 91:105–126.
  * [Ouyang et al., 2022] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. (2022).  Training language models to follow instructions with human feedback.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Pérez et al., 2019] Pérez, J., Marinković, J., and Parceló, P. (2019).  On the Turing completeness of modern neural network architectures.  In International Conference on Learning Representations (ICLR).
  * [Radford et al., 2019] Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019).  Language models are unsupervised multitask learners.
  * [Schulman et al., 2022] Schulman, J., Zoph, B., Kim, C., Hilton, J., Menick, J., Weng, J., Uribe, J. F. C., Fedus, L., Metz, L., Pokorny, M., Lopes, R. G., Zhao, S., Vijayvergiya, A., Sigler, E., Perelman, A., Voss, C., Heaton, M., Parish, J., Cummings, D., Nayak, R., Balcom, V., Schnurr, D., Kaftan, T., Hallacy, C., Turley, N., Deutsch, N., and Goel, V. (2022).  ChatGPT: Optimizing language models for dialogue.  https://openai.com/blog/chatgpt.
  * [Shannon, 1956] Shannon, C. (1956).  A universal Turing machine with two internal states.  Automata Studies, Annals of Mathematics Studies, 34:157–165.
  * [Siegelmann and Sontag, 2019] Siegelmann, H. and Sontag, E. (2019).  On the computational power of neural nets.  In Conference on Learning Theory (COLT).
  * [Sipser, 2013] Sipser, M. (2013).  Introduction to the Theory of Computation.  Cengage Learning, 3rd edition.
  * [Turing, 1937] Turing, A. (1937).  On computable numbers, with an application to the Entscheidungsproblem.  Proceedings of the London Mathematical Society, 2, 42:230–265.
  * [von Neumann, 1945] von Neumann, J. (1945).  First draft of a report on the EDVAC.
  * [Wei et al., 2022a] Wei, C., Chen, Y., and Ma, T. (2022a).  Statistically meaningful approximation: a case study on approximating Turing machines with Transformers.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Wei et al., 2022b] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., and Zhou, D. (2022b).  Chain of thought prompting elicits reasoning in large language models.  In Advances in Neural Information Processing Systems (NeurIPS).
  * [Weiss et al., 2018] Weiss, G., Goldberg, Y., and Yahav, E. (2018).  On the practical computational power of finite precision RNNs for language recognition.  In Conference of the Association for Computational Linguistics (ACL).
  * [Wolfram, 2002] Wolfram, S. (2002).  A New Kind of Science.  Wolfram Media.
  * [Zhou et al., 2022] Zhou, D., Schärli, N., How, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q., and Chi, E. (2022).  Least-to-most prompting enables complex reasoning in large language models.  arXiv 2205.10625.