TRANSACTIONS OF THE
AMERICAN MATHEMATICAL SOCIETY
Volume 373, Number 5, May 2020, Pages 3085–3115
https://doi.org/10.1090/tran/7915
Article electronically published on February 20, 2020

ON THE COMPUTATIONAL COMPLEXITY OF ALGEBRAIC
NUMBERS: THE HARTMANIS–STEARNSPROBLEM REVISITEDBORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC
Abstract. We consider the complexity of integer base expansions of algebraic
irrational numbers from a computational point of view. A major contribution
in this area is that the base-b expansion of algebraic irrational real numbers
cannot be generated by ﬁnite automata. Our aim is to provide two naturalgeneralizations of this theorem. Our main result is that the base-b expansion ofalgebraic irrational real numbers cannot be generated by deterministic pushdown automata. Incidentally, this completely solves the Hartmanis–Stearns
problem for the class of multistack machines. We also conﬁrm an old claimof Cobham from 1968 proving that such real numbers cannot be generated by
tag machines with dilation factor larger than one. In order to stick with themodern terminology, we also show that the latter generate the same class ofreal numbers as morphisms with exponential growth.

1. Introduction
An old source of frustration for mathematicians arises from the study of integer
base expansions of classical constants like√2 = 1.414 213 562 373 095 048 801 688 724 209 698 078 569 · · ·or
π = 3.141 592 653 589 793 238 462 643 383 279 502 884 197 · · · .
While these numbers admit very simple geometric descriptions, a close look attheir digital expansion suggests highly complex phenomena. Over the years, diﬀerent ways have been envisaged to formalize this old problem. This recurring theme
appeared in particular in three fundamental papers, using the language of probability according to É. Borel [17], the language of dynamical systems according toMorse and Hedlund [37], and the language of Turing machines according to Hartmanis and Stearns [30]. Each of these points of view leads to a diﬀerent assortmentof challenging conjectures. As the title of this paper suggests, the present work
focuses on the latter approach. It is addressed to researchers interested both innumber theory and theoretical computer science. In this respect, we took care to
make the paper as self-contained as possible, and hopefully readable by members
from these diﬀerent communities.
Received by the editors October 3, 2017, and, in revised form, October 31, 2018, and March
13, 2019.
2010 Mathematics Subject Classiﬁcation. Primary 11B85, 11J81, 68Q45, 68R15, 11J87.
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No
648132.
c
2020
American Mathematical Society

3085This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3086

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

After the seminal work of Turing [47], real numbers can be coarsely divided
into two classes. On one side we ﬁnd the computable real numbers, those whosebase-b expansion can be produced by a Turing machine, while on the other side lie
uncomputable real numbers, which will remain forever beyond the ability of computers. Note that, though most real numbers belong to the second class, classicalmathematical constants are usually computable. This is, in particular, the casefor any algebraic number. However, among computable numbers, some are quite
easy to compute, while others seem to have an inherent complexity that makes
them diﬃcult to compute. In 1965, Hartmanis and Stearns [30] investigated thefundamental question of how hard a real number may be to compute, introducing
the now classical time complexity classes. The notion of time complexity takes into
account the number T (n) of operations needed by a multitape deterministic Turingmachine to produce the ﬁrst n digits of the expansion. In this regard, a real number is considered all the more simple as its base-b expansion can be produced very
quickly by a Turing machine. At the end of their paper, Hartmanis and Stearns
suggested the following problem.
Problem HS. Do there exist irrational algebraic numbers for which the ﬁrst nbinary digits can be computed in O(n) operations by a multitape deterministic
Turing machine?
Let us brieﬂy recall why Problem HS is still open and likely diﬃcult to solve. On
the one hand, all known approaches to compute the base-b expansion of algebraic
irrational numbers eﬃciently intimately rely on the cost of the multiplication M (n)of two n-digit numbers (see, for instance, [18]). This operation is computable inquasilinear time, that is, computable in O(n logj n) operations for some positive
integer j. However, to determine whether M (n) = O(n) remains a famous open
problem in this area. On the other hand, a negative answer to Problem HS, which
may be the less surprising issue according to [26], would contain a powerful statement about transcendence. A very special instance is the transcendence of the three
simple irrational real-time computable numbers
∞
∞
∞



1
1
1
,
,
and
·
n!
n2
n3
2
2
2
n=1
n=1
n=1

Of course, for the ﬁrst one, Liouville’s inequality [34] easily does the job. But
the transcendence of the second number only dates back to 1996 [16, 28] and its
proof requires the deep work of Nesterenko on the algebraic independence of valuesof Eisenstein series [39]. Finally, the transcendence of the third number remains
unknown.
In 1968, Cobham [26] (also see [24, 25]) was the ﬁrst to consider the restrictionof the Hartmanis-Stearns problem to some classes of Turing machines. The modelof computation he originally investigated is the so-called tag machine. Though
this model has some historical interest, this terminology is not much used today
by the computer science community. However, the class of sequences output by
tag machines precisely corresponds to the class of morphic sequences, a well-known
object of interest for both mathematicians and computer scientists. The latterare especially used in combinatorics on words and symbolic dynamics (see, forinstance, [12, 42, 43]). The equivalence between the class of sequences output by
tag machines and the class of morphic sequences follows from [26, 27]. See also,This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3087

for instance, [12, Chapter 7] concerning the more modern terminology of morphic
sequences. In what follows, we will present our result using the terminology ofmorphic sequences but, for the interested reader, we describe the connection withtag machines in Section 5.1.
In his paper, Cobham stated two main theorems without proof and only gavesome hints that these statements should be deduced from a general transcendence
method based on functional equations, now known as Mahler’s method. His ﬁrst
claim was ﬁnally conﬁrmed by the ﬁrst author and Bugeaud [3], but using a totallydiﬀerent approach based on a p-adic version of the subspace theorem (see [3, 8]).
Very recently, some advances in Mahler’s method [10, 41] permitted completion of
the proof originally envisaged by Cobham.
Theorem AB (Cobham’s ﬁrst claim). The base-b expansion of an algebraic irrational number cannot be generated by a uniform morphism or, equivalently, by aﬁnite automaton.
For deﬁnitions of real numbers generated by ﬁnite automata and by uniform
morphisms, we refer the reader to Deﬁnition 2.3 and Section 2.2.
Remark 1.1. Theorem AB actually refers to two conceptually quite diﬀerent modelsof computation: uniform morphisms and ﬁnite automata. There are two naturalways a multitape deterministic Turing machine can be used to deﬁne computable
numbers. First, it can be considered as an enumerator, which means that themachine produces one by one all the digits of a real number ξ in a given base b on
its output tape. Problem HS originally referred to the model of enumerators. In
the other model, referred to as a Turing transducer, the machine is fed with some
input representing a positive integer n and has to produce on its output tape thenth digit in the base-b expansion of ξ. In Theorem AB, uniform morphisms (ororiginally uniform tag machines) are enumerators while ﬁnite automata are usedas transducers. Note that, used as enumerators, ﬁnite automata can only produce
eventually periodic sequences of digits and thus rational numbers (see, for instance,[12, Theorem 5.7.1]). In contrast, used as transducers, ﬁnite automata output theinteresting class of automatic sequences (see [12]). The fact that these two models
are equivalent is due to Cobham [27].
Theorem AB is the main contribution to date toward a negative solution to
Problem HS. In this paper, we show that the approach developed in [3, 8] leads to
two interesting generalizations of this result. Our ﬁrst generalization is concernedwith enumerators. In this direction, we conﬁrm the second claim of Cobham.
Theorem 1.2 (Cobham’s second claim). The base-b expansion of an algebraic
irrational number cannot be generated by a morphism with exponential growth.
For the deﬁnition of a real number generated by a morphism with exponential
growth, we refer the reader to Deﬁnition 2.6. We stress that, as stated above,
Theorem 1.2 also appeared in the Thèse de Doctorat of Julien Albert [11]. In orderto provide a self-contained proof of Cobham’s second claim, which was originallyformulated in terms of tag machines, we will complete and reprove with permission
some content of [11] in Section 4.1. The fact that Theorem 1.2 is equivalent toCobham’s second claim will be proved in Section 5.1.
Our second and main generalization of Theorem AB is concerned with transducers. We consider a classical computation model called the deterministic pushdown

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3088

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

automaton. It is of great importance on the one hand for theoretical aspects because of Chomsky’s hierarchy [23] in formal language theory, and on the other forpractical applications, especially in parsing (see for instance [31,46]). Roughly, sucha device is a ﬁnite automaton with an unbounded memory organized as a stack,that is, as an LIFO data structure. The acronym LIFO stands for Last-In-First-Out
and reﬂects the way symbols can be stored and removed from the stack. In what
follows, all stacks are LIFO. Our main result is the following.
Theorem 1.3. The base-b expansion of an algebraic irrational number cannot be
generated by a deterministic pushdown automaton.
For the deﬁnition of a real number generated by a deterministic pushdown automaton, we refer the reader to Deﬁnition 2.12. In Section 5.2, we use Theorem 1.3
to revisit the Hartmanis–Stearns problem as follows: instead of a time constraint,
we impose a restriction based on the way the memory may be stored by Turing machines. This leads us to consider a classical computation model called a multistackmachine. It corresponds to a version of the deterministic Turing machine where
the memory is simply organized as stacks. It is as general as the Turing machine if
one allows two or more stacks. Furthermore the one-stack machine turns out to beequivalent to the deterministic pushdown automaton, while a zero-stack machine isjust the ﬁnite automaton of Theorem AB, that is, a machine with a strictly ﬁnite
memory only stored in the ﬁnite-state control. Incidentally, Theorems AB and 1.3
turn out to completely solve the Hartmanis–Stearns problem for multistack machines. Our approach also provides a method to prove the transcendence of somereal numbers generated by linearly bounded Turing machines (see the example in
Section 5.3).
This paper is organized as follows. Deﬁnitions related to ﬁnite automata, morphisms, and pushdown automata are given in Section 2. The useful combinatorialtranscendence criterion of [8], on which our results are based, is recalled in Section 3. Section 4 is devoted to the proofs of Theorems 1.2 and 1.3. In connection
with these results, two models of computation are discussed in Section 5: the tag
machine and the multistack machine. Finally, Section 6 is devoted to concluding
remarks regarding factor complexity, some quantitative aspects of this method, andcontinued fractions.
2. Finite automata, morphic sequences, and pushdown automata
In this section, we give deﬁnitions for a real number to be generated by a ﬁnite
automaton, a morphism, and a deterministic pushdown automaton. This provides
a precise meaning to Theorems AB, 1.2, and 1.3.
Throughout this paper, we will use the following notation. An alphabet A is a
ﬁnite set of symbols, also called letters. A ﬁnite word over A is a ﬁnite sequenceof letters in A or, equivalently, an element of A∗ , the free monoid generated by A.
The length of a ﬁnite word W , that is, the number of symbols in W , is denoted
by |W |. We let  denote the empty word, the neutral element of A∗ . We let A+
denote the set of ﬁnite words of positive length over A. If a is a letter and W aﬁnite word, then |W |a stands for the number of occurrences of the letter a in W .
Let k ≥ 2 be a natural number. We let Σk denote the alphabet {0, 1, . . . , k − 1}.
Given a positive integer n, we set nk := wr wr−1 · · · w0 for the canonical base-k
expansion of n (written from most to least signiﬁcant digit), which means that

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS3089

n = ri=0 wi ki with wi ∈ Σk and wr = 0. Note that by convention 0k := .
Let Rk := (Σk \ {0}) Σ∗k denote the language of all canonical base-k expansion of
positive integers. For every positive integer n, there is a unique word w in Rk suchthat nk = w.Conversely, if w := w0 · · · wr is a ﬁnite word over the alphabet Σk ,we set [w]k := ri=0 wr−i ki . Given a real number ξ ∈ [0, 1), we let ξk := 0.a1 a2 · · ·−idenote the canonical base-k expansion of ξ, which means that ξ = +∞withi=1 ai kai ∈ Σk and ai = k − 1 for inﬁnitely many indices i. The usual notation {x}, x ,and x , respectively, stands for the fractional part, the ﬂoor, and the ceiling of thereal number x.
2.1. Finite automata and automatic sequences. A sequence a := (an )n≥0with values in a ﬁnite set is k-automatic if it can be generated by a ﬁnite automaton used as a transducer. This means that there exists a ﬁnite-state machine (adeterministic ﬁnite automaton with output) that takes as input the base-k expansion of n and produces as output the symbol an . We use the following convention.
Inputs are read from left to right, that is, starting from the most signiﬁcant digit.
In this paper, this convention is used for all machines which are used as a transducer(k-automata, k-pushdown automata, k-multistack machines, one-way transducerlike k-machines).
Let us give now a formal deﬁnition of a k-automatic sequence. Let k ≥ 2 be anatural number. A k-automaton is deﬁned as a 6-tuple A := (Q, Σk , δ, q0 , Δ, τ ),where
• Q is a ﬁnite set called the set of states,• Σk is called the set of input symbols,• δ : Q × Σk → Q is called the transition function,• q0 ∈ Q is called the initial state,• Δ is a ﬁnite set called the set of output symbols,• τ : Q → Δ is called the output function.
Given a state q in Q and a ﬁnite word w := w1 w2 · · · wn over the alphabet Σk , wedeﬁne δ(q, w) recursively by δ(q, ) = q and δ(q, w) = δ(δ(q, w1 w2 · · · wn−1 ), wn ).
Deﬁnition 2.1. Let A := (Q, Σk , δ, q0 , Δ, τ ) be a k-automaton. The output sequence produced by A is the sequence (τ (δ(q0 , nk )))n≥0 . Such a sequence is calleda k-automatic sequence. A sequence or an inﬁnite word is said to be automatic if
it is k-automatic for some integer k ≥ 2.
Example 2.2. By a classical result of Lagrange, it is known that every non-negative
integer can be written as the sum of four perfect squares. It is optimal in the sensethat some natural numbers cannot be written as the sum of only three squares.
More precisely, Legendre proved that
∃ a, b, c | n = a2 + b2 + c2 ⇐⇒  ∃ i, j | n = 4i (8j + 7) ,where n, a, b, c, i, j are non-negative integers. As a consequence, the binary sequences := (sn )n≥0 deﬁned by sn = 1 if n can be written as the sum of three squares and
sn = 0 otherwise is 2-automatic. See Figure 2.1 for a ﬁnite automaton generating
the sequence s.
Deﬁnition 2.3. A real number ξ can be generated by a deterministic k-automaton
A if, for some integer b ≥ 2, one has {ξ}b = 0.a1 a2 · · · , where (an )n≥0 corresponds
to the output sequence produced by A.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3090

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

0
0
0

A/1

C/1
B/1

1
1

1

1

1
0

0
F/0

E/1

D/0

0
1
Figure 2.1. A 2-automaton generating the sequence s.
Remark 2.4. Note that a0 is not used in Deﬁnition 2.3. We could also have requiredthat (an+1 )n≥0 be produced by A. As the set of k-automatic sequences is invariant
under shift [12, Corollary 6.8.5], this would not change the class of real numbers
generated by deterministic k-automata.
Theorem AB thus implies that the binary number
ξ0 := 1.111 111 011 111 110 111 111 101 111 011 011 111 110 · · ·generated by the 2-automaton of Figure 2.1 is transcendental.
2.2. Morphic sequences. Here we recall some basic deﬁnitions. Let A be a ﬁnite
alphabet. A map from A to A∗ naturally extends to a map from A∗ into itself calledan (endo)morphism. Given two alphabets A and B, a map from A to B naturally
extends to a map from A∗ into B ∗ called a coding or letter-to-letter morphism. A
morphism σ over A is said to be k-uniform if |σ(a)| = k for every letter a in A,
and just uniform if it is k-uniform for some k. A useful object associated with amorphism σ is the so-called incidence matrix of σ, denoted by Mσ . We ﬁrst needto choose an ordering of the elements of A, say A = {a1 , a2 , . . . , ad }, and then Mσis deﬁned by∀i, j ∈ {1, . . . , d}, (Mσ )i,j := |σ(aj )|ai .
The choice of the ordering has no importance. A morphism σ over A is said tobe prolongable on a if σ(a) = aW for some word W and if the length of the word
σ n (a) tends to inﬁnity with n. Then the wordσ ω (a) := lim σ n (a) = aW σ(W )σ 2 (W ) · · ·n→∞is the unique ﬁxed point of σ that begins with a. An inﬁnite word obtained by
iterating a prolongable morphism σ is said to be pure morphic. The image of apure morphic word under a coding is a morphic word. Thus, to deﬁne a morphic
word a, one needs a 5-tuple T := (A, σ, a, B, ϕ) such that a = ϕ(σ ω (a)), where• A is a ﬁnite set of symbols called the internal alphabet,• a is an element of A called the starting symbol,• σ is a morphism of A∗ prolongable on a,• B is a ﬁnite set of symbols called the external alphabet,• ϕ is a letter-to-letter morphism from A to B.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3091

When σ is uniform (resp., k-uniform), the sequence a is said to be generated bya uniform (resp., k-uniform) morphism.
Deﬁnition 2.5. A morphism σ is said to have exponential growth if the spectral
radius of the matrix Mσ is larger than one. When σ has exponential growth andall letters of A appear in σ ω (a), the sequence a := ϕ(σ ω (a)) is said to be generated
by a morphism with exponential growth.
Deﬁnition 2.6. A real number ξ can be generated by a morphism with exponential
growth if, for some integer b ≥ 2, one has {ξ}b = 0.a1 a2 · · · , where a := (an )n≥0
can be generated by a morphism with exponential growth.
Theorem 1.2 thus implies the transcendence of the ternary numberξ1 := 0.212 012 202 101 222 021 201 202 101 222 202 121 22 · · ·whose expansion is the sequence a := ϕ1 (σ1ω (a)), where σ1 (a) = acb, σ1 (b) = abc,
σ1 (c) = c, ϕ1 (a) = 0, ϕ1 (b) = 1, and ϕ1 (c) = 2. One can check that σ1 has
exponential growth for the spectral radius of Mσ1 is 2. In contrast, Theorem 1.2
2
does not apply to the binary number 2−n . Though this number can be generated
by the morphism σ2 deﬁned below, the latter has non-exponential growth. Indeed
the characteristic sequence of squares can be obtained as ϕ2 (σ2ω (a)) where σ2 (a) =ab, σ2 (b) = ccb, σ2 (c) = c, ϕ2 (a) = ϕ2 (b) = 1, and ϕ2 (c) = 0. One can check easily
that the spectral radius of Mσ2 is equal to 1.
Remark 2.7. Following Cobham [26], there is no loss of generality to assume thatthe internal morphism σ is a non-erasing morphism, which means that no letter
is mapped to the empty word. Indeed, if an inﬁnite word can be generated by anerasing morphism, then there also exists a non-erasing morphism that can generate
it. From now on, we will only consider non-erasing morphisms.
It is worth mentioning that the class of sequences generated by uniform morphisms is especially relevant because of the following result of Cobham [27].
Proposition C. A sequence is k-automatic if and only if it can be generated bysome k-uniform morphism.
Furthermore, the proof of Proposition C is completely constructive and provides
a simple way to go from k-uniform morphisms to k-automata and vice versa. This
general feature is exempliﬁed below. For a complete treatment see [27] or [12,Chapter 6].

0

0
1
q0 /0

q1 /1
1

Figure 2.2. A 2-automaton generating Thue–Morse sequence.
Example 2.8. The Thue–Morse sequence t := (tn )n≥0 is probably the most famous example among automatic sequences. It is deﬁned as follows: tn = 0 if
the sum of the binary digits of n is even, and tn = 1 otherwise. It can be

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3092

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

generated by the following ﬁnite 2-automaton, represented in Figure 2.2: A :=({q0 , q1 }, {0, 1}, δ, q0 , {0, 1}, τ ), where δ(q0 , 0) = δ(q1 , 1) = q0 , δ(q0 , 1) = δ(q1 , 0) =q1 , τ (q0 ) = 0 and τ (q1 ) = 1. The Thue–Morse sequence can as well be generated by a 2-uniform morphism, for one has t = ϕ(σ ω (q0 )), where σ(q0 ) = q0 q1 ,σ(q1 ) = q1 q0 , ϕ(q0 ) = 0, ϕ(q1 ) = 1.
2.3. Pushdown automata. A pushdown automaton is a classical device, but mostoften used in formal language theory as an acceptor, that is, a machine that can accept or reject ﬁnite words and thus deﬁnes languages, namely context-free languages(see, for instance, [13, 14, 31]). In particular, a classical reference about deterministic context-free languages and deterministic pushdown automata is [31, Chapter
10]. Our point of view here is slightly diﬀerent, for we use the pushdown automaton
as a transducer, that is, a machine that associates a symbol with every ﬁnite word
over a given input alphabet.
Formally, a k-pushdown automaton is a complete deterministic pushdown automaton with output, or DPAO for short. It is deﬁned as a 7-tuple M := (Q, Σk , Γ,δ, q0 , Δ, τ ), where• Q is a ﬁnite set called the set of states.
• Σk := {0, 1, . . . , k − 1} is called the set of input symbols.
• Γ is a ﬁnite set called the set of stack symbols.
For convenience, a special symbol # denotes the empty word of Γ∗ , i.e., theempty stack.
The set Q × Γ∗ is called the set of (internal) conﬁgurations.
• δ : E ⊂ Q × (Γ ∪ {#}) × (Σk ∪ {}) → Q × Γ∗ is called the transition
function.
• q0 ∈ Q is called the initial state and (q0 , #) is called the initial conﬁguration.
• Δ is a ﬁnite set called the set of output symbols.
• τ : Q × (Γ ∪ {#}) → Δ is called the output function.
Furthermore, the transition function satisﬁes the following conditions:• Determinism assumption: If (q, s, ) belongs to E for some (q, s) ∈ Q ×(Γ ∪ {#}), then no (q, s, a) with a ∈ Σk belongs to E. In this case we saythat M has an -move from internal conﬁguration (q, s).
• Completeness assumption: If (q, s, ) does not belong to E for some (q, s) ∈Q × (Γ ∪ {#}), then {q} × {s} × Σk ⊂ E.
• Finiteness assumption on -moves: There does not exist an inﬁnite sequenceof internal conﬁgurations (qi , Si )i≥1 such that δ(qi , si , ) = (qi+1 , Xi ) for alli ≥ 1, where si is the ﬁrst symbol in Si , or # if Si is empty, Si = Si si , andSi+1 = Si Xi . This assumption is in particular satisﬁed when all -moves
decrease the stack height (see Remark 2.13).
Remark 2.9. Notice that δ being a function is also a part of the determinism assumption. In a non-deterministic k-pushdown automaton, δ would be deﬁned as asubset of Q × (Γ ∪ {#}) × (Σk ∪ {}) × Q × Γ∗ .
We now want to make sense of the computation τ (δ(q0 , #, W )) for any input
word W in Σ∗k . First, the transition function δ of a k-pushdown automaton cannaturally be extended to a subset of Q × Γ∗ × (Σk ∪ {}) by setting∀S ∈ Γ∗ , δ(q, Ss, a) = (q  , SX)

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3093

when δ(q, s, a) = (q  , X) with s ∈ Γ (i.e., s = #). After reading the symbol a,the pushdown automaton could reach a conﬁguration (q, S) from which -moves
are possible. In such a case, the determinism assumption forces the pushdown
automaton to perform all possible -moves before reading the next input symbol,
and the ﬁniteness assumption ensures that this will eventually stop. We stress that
this appears to be a classical convention (see the discussion in [14, Section 5.2])
which can be formalized by using, instead of δ, the function δ deﬁned as follows:⎧⎨ δ(q, S, a) = δ(δ(q, S, a), );δ(q, S, ) = (q, S)
if (q, S, ) ∈/ E;⎩
δ(q, S, ) = δ(δ(q, S, ), )
if (q, S, ) ∈ E.
Then δ can be extended to a subset of Q × Γ∗ × Σ∗k by settingδ(q, S, wa) = δ δ(q, S, w), a .
This means in particular that M scans its inputs from left to right. We also extend
the output function τ to Q × Γ∗ by simply setting τ (q, Ss) = τ (q, s) for q ∈ Q,s ∈ Γ, and S ∈ Γ∗ .
Deﬁnition 2.10. Let M := (Q, Σk , Γ, δ, q0 , Δ, τ ) be a k-pushdown automaton.
The sequence (τ (δ(q0 , #, nk )))n≥0 is called the output sequence produced by M.
This class of sequences is discussed in [22]. They form a subclass of the contextfree sequences (see [22, 38]).
Example 2.11. Usually a deterministic pushdown automaton is represented asa ﬁnite graph whose vertices are labelled by the elements of Q and whose edges
are labelled by transitions as follows: δ(q, s, a) = (q  , X) is represented by the edge(a,s|X)q −−−−−→ q  . An example of such internal representation is given by the 2-pushdown
automaton A in Figure 2.3. It outputs the binary sequencea := 1110111001101000011111101110100000010110 · · ·whose nth binary digit is 1 if the diﬀerence between the number of occurrences ofthe digits 0 and 1 in the binary expansion of n is at most 1, and is 0 otherwise.

(0, #|X),(0, X|XX),(1, X|#)(1, #|#)
q−1(1, #|#)
q0(0, #|#)

q1(0, #|#)(1, #|X),(1, X|XX),(0, X|#)

Figure 2.3. A 2-pushdown automaton producing the binary expansion of ξ2 .
This automaton works as follows. Being in state q0 means that the part of the
input word that has been already read contains as many 1’s as 0’s. On the other
hand, being in state q1 means that the part of the input word that has been alreadyread contains more 1’s than 0’s, while being in state q−1 means that it contains
more 0’s than 1’s. Furthermore, in any of these two states, the diﬀerence between
the number of 0’s and 1’s (in absolute value) is one more than the number of X’s in
the stack. Thus, the diﬀerence between the number of occurrences of the symbols 1
and 0 in the input word is at most 1 if and only if the reading ends with an empty

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3094

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

stack (regardless of the ending state). Choosing the output function accordingly,
we see that A produces the inﬁnite word a.
Note that, formally, the pushdown automaton described above is deﬁned as
A := ({q0 , q1 , q−1 }, Σ2 , {X}, δ, q0 , {0, 1}, τ ), where the transition function δ is givenbyδ(q0 , #, 0) = (q−1 , #),δ(q0 , #, 1) = (q1 , #),δ(q0 , X, 0) = (q0 , #),δ(q0 , X, 1) = (q0 , #),δ(q1 , #, 0) = (q0 , #),δ(q1 , #, 1) = (q1 , X),
δ(q1 , X, 0) = (q1 , #),δ(q1 , X, 1) = (q1 , XX),δ(q−1 , #, 0) = (q−1 , X),δ(q−1 , #, 1) = (q0 , #),δ(q−1 , X, 0) = (q−1 , XX),δ(q−1 , X, 1) = (q−1 , #),and where the output function τ is deﬁned byτ (q0 , #) = τ (q1 , #) = τ (q−1 , #) = 1
andτ (q0 , X) = τ (q1 , X) = τ (q−1 , X) = 0 .
The two transitions from q0 to q0 with stack symbol X ensure completeness of theautomaton, but they are never used in actual computations, so we omitted themin Figure 2.3.
Deﬁnition 2.12. A real number ξ can be generated by a deterministic k-pushdown
automaton M if, for some integer b ≥ 2, one has {ξ}b = 0.a1 a2 · · · , where (an )n≥0
corresponds to the output sequence produced by M.
Theorem 1.3 thus implies the transcendence of the binary numberξ2 := 1.110 111 001 101 000 011 111 101 110 100 000 010 110 · · ·whose binary expansion is the inﬁnite word a of Example 2.11.
Remark 2.13. About -moves.— Since we only consider deterministic pushdown
automata, we can assume without loss of generality that all -moves decrease thestack height, that is, δ(q, s, ) = (q  , X) implies s = # and X = # (see, for instance,[14, Proposition 5.4], or [31, Exercise 10.2(a)]).
Normal forms.— Further assumptions may be made without loss of generality.
For instance, we can assume that the transition function has only moves of the form
δ(q, s, a) = (q  , #), known as pop moves, and of the form δ(q, s, a) = (q  , ss ), withs ∈ Γ, known as push moves (see [31, Lemma 10.2]).
About input words.— In our model of k-pushdown automaton, we choose to feed
our machines only with the canonical base-k expansion of each non-negative integer
n. Instead, we could as well imagine to ask that τ (δ(q0 , #, w)) remain the samefor all words w ∈ Σ∗k such that [w]k = n, that is, τ (δ(q0 , #, w)) = τ (δ(q0 , #, 0j w))
for every natural number j. Such a change would not aﬀect the class of output
sequences produced by k-pushdown automata. The discussion is similar to the caseof the k-automaton and we refer to [12, Chapter 5] for more details.
Our second remark concerning inputs is more important. In our model, the kpushdown automaton scans the base-k expansion of a positive integer n startingfrom the most signiﬁcant digit. This corresponds to the usual way humans read
numbers, that is from left to right. In the case of the k-automaton, this choice is ofno consequence because both ways of reading are known to be equivalent. However,this is no longer true for k-pushdown machines, as the class of deterministic context
free languages is not closed under reversal (see, for instance, [31, p. 281]).

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3095

About uniqueness.— There always exist several diﬀerent k-pushdown automata
producing the same output. In particular, it is possible to choose one with a single
state (by encoding the state into the stack). The 2-automaton given in Figure 2.3
is certainly not the smallest one with respect to the number of states, but it makes
the process of computation more transparent and it only uses one ordinary stacksymbol.
3. A combinatorial transcendence criterion
In this section, we recall the fundamental relation between Diophantine approximation and repetitive patterns occurring in integer base expansions of real numbers.
Let A be an alphabet and let W be a ﬁnite word over A. For any positive integerm, we write W m for the word
W ···Wm times(the concatenation of the word W repeated m times). More generally, for any
positive real number x, W x denotes the word W x W  , where W  is the preﬁx of
W of length {x}|W | . The following natural measure of periodicity for inﬁnite
words was introduced in [4] (also see [1, 9]).
Deﬁnition 3.1. The Diophantine exponent of an inﬁnite word a is deﬁned as thesupremum of the real numbers ρ for which there exist arbitrarily long preﬁxes ofa that can be factorized as U V α , where U and V are two ﬁnite words (U possibly
empty) and α is a real number such that|U V α |≥ ρ.
|U V |The Diophantine exponent of a is denoted by dio(a).
Of course, for any inﬁnite word a one has the following relation:
1 ≤ dio(a) ≤ +∞.
Furthermore, dio(a) = +∞ for an eventually periodic word a, but the converse is
not true. There is some interesting interplay between the Diophantine exponent
and Diophantine approximation, which is actually responsible for the name of the
exponent. Let ξ be a real number whose base-b expansion is 0.a1 a2 · · · . Set a :=a1 a2 · · · . Let us assume that the word a begins with a preﬁx of the form U V α ,with V = . Set q := b|U| (b|V | − 1). A simple computation shows that there exists
an integer p such that
p/qb = 0.U V V V · · · .
Since ξ and p/q have the same ﬁrst |U V α | digits in their base-b expansion, we
obtain thatp1
ξ−
< |UV α |qband thus
1
p
(3.1)
< ρ,
ξ−
q
q
where ρ := |U V α |/|U V |.
We do not claim here that p/q is written in lowest terms. Actually, it may
happen that the gcd of p and q is quite large but (3.1) still holds in that case.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3096

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

By Deﬁnition 3.1, it follows that for every ρ < dio(a), there exist inﬁnitely many
rational numbers p/q such that
ξ−

1
p
< ρ·
q
q

Note that when dio(a) < 2, such approximations look quite bad, for the existence ofmuch better ones is ensured by the theory of continued fractions or by the Dirichlet
pigeonhole principle. Quite surprisingly, the inequality dio(a) > 1 is already enoughto conclude that ξ is either rational or transcendental. This powerful combinatorialtranscendence criterion, proved in [8] and restated in Proposition ABL, emphasizes
the relevance of the Diophantine exponent for our purpose.
Proposition ABL. Let ξ be a real number with {ξ}b := 0.a1 a2 · · · . Suppose thatdio(a) > 1 where a := a1 a2 · · · . Then ξ is either rational or transcendental.
Proposition ABL is obtained as a consequence of the p-adic subspace theorem.
It is the key tool for proving Theorem AB, and it will be the key tool for proving
Theorems 1.2 and 1.3 as well.
4. Proof of Theorems 1.2 and 1.3
In this section, we prove our two main results.
4.1. Proof of Theorem 1.2. In order to prove Theorem 1.2, we ﬁrst need thefollowing deﬁnition.
Deﬁnition 4.1. Let A be a ﬁnite set and let σ be a morphism of A∗ . A letterb ∈ A is said to have maximal growth if there exists a real number C such that
|σ n (c)| ≤ C|σ n (b)|for every letter c ∈ A and every positive integer n.
Lemma 4.2. Let A be a ﬁnite set and a ∈ A. Let σ be a morphism of A∗ prolongable on a and such that all letters of A appear in σ ω (a). Then the letter a has
maximal growth. Let θ denote the spectral radius of Mσ . Furthermore, there exist
a non-negative integer and two positive real numbers c1 and c2 such thatc1 n θ n < |σ n (a)| < c2 n θ n(4.1)
for every positive integer n.

Proof. Let c be a letter occurring in σ ω (a). Then c also occurs in σ r (a), for somepositive integer r. Then|σ n (c)| ≤ |σ n+r (a)| = |σ r (σ n (a))| ≤ Mσr ∞ |σ n (a)| ,where  · ∞ stands for the usual inﬁnite norm. This shows that a has maximal
growth. Now recall that by a classical result of Salomaa and Soittola (see, forinstance, Theorem 4.7.15 in [21]), there exist a non-negative integer , a real numberβ ≥ 1, and two positive real numbers c1 and c2 such that
(4.2)

c1 n β n < |σ n (a)| < c2 n β n

for every positive integer n. Since a has maximal growth, a classical theorem onmatrices due to Gelfand (see, for instance, [21]) implies that β must be equal to θ,
the spectral radius of the incidence matrix of σ.
This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3097

Proposition 4.3. Let a be an inﬁnite sequence that can be generated by a morphismwith exponential growth. Then dio(a) > 1.
Proof. Let a be an inﬁnite sequence that can be generated by a morphism withexponential growth. Then a = ϕ(σ ω (a)) for some morphism σ with exponential
growth deﬁned over a ﬁnite alphabet A, and some coding ϕ. Furthermore, we recall
that the spectral radius θ of the incidence matrix Mσ satisﬁes θ > 1. Set u := σ ω (a).
Since by deﬁnition σ is prolongable on a and all letters of A appear in u, Lemma 4.2
implies that a has maximal growth and that there exist a non-negative integer
and two positive real numbers c1 and c2 such thatc1 n θ n < |σ n (a)| < c2 n θ n(4.3)
for every positive integer n.

Remark 4.4. If a ∈ A is a letter of maximal growth, and b ∈ A is not a letter ofmaximal growth, then for any positive real number ε, one has |σ n (b)| < ε|σ n (a)|for suﬃciently large n.
We now prove that there are inﬁnitely many occurrences of letters with maximal growth in u. Let us argue by contradiction. If there are only ﬁnitely manyoccurrences of letters with maximal growth, then there exists a positive integer n0such that u = σ n0 (a)w where w is an inﬁnite word that contains no letter withmaximal growth. Since θ > 1, there is an integer m0 such that
(4.4)

c2 /θ m0 < c1 /2.

Let V0 denote the unique ﬁnite word such that σ n0 +m0 (a) = σ n0 (a)V0 . Then forevery positive integer n we get that
|σ n+n0 +m0 (a)| = |σ n+n0 (a)| + |σ n (V0 )| ≤ c2 (n + n0 ) θ n+n0 + |σ n (V0 )| .
Given ε > 0, we have that |σ n (V0 )| < εn θ n for all n suﬃciently large, since byconstruction V0 contains no letter with maximal growth. Choosing ε = c1 /2, wethen infer from (4.4) that
|σ n+n0 +m0 (a)|< c1 ,(n + n0 + m0 ) θ n+n0 +m0
when n is large enough. This provides a contradiction with (4.3).
Since there are inﬁnitely many occurrences in u of letters with maximal growth,
the pigeonhole principle ensures the existence of such a letter b that occurs at least
twice in u. In particular, there exist two possibly empty ﬁnite words U and V suchthat U bV b is a preﬁx of u. Set r := |U |, s := |bV |, and for every non-negative
integer n, Un := σ n (U ), Vn := σ n (bV ). Since by deﬁnition u is ﬁxed by σ, we getthat Un Vnδn is a preﬁx of u, where δn := 1 + |σ n (b)|/|σ n (bV )|. Since b has maximal
growth, there exists a positive real number c3 such that
|σ n (c)| ≤ c3 |σ n (b)|for every letter c in u. We thus obtain that|Un Vnδn ||σ n (b)|
1
=1+ n
≥1+
> 1.
|Un Vn ||σ (U bV )|c3 (r + s)
This proves that dio(u) > 1. By deﬁnition, one has a := ϕ(u). It thus follows thatdio(a) ≥ dio(u) > 1, because applying a coding to an inﬁnite word cannot decrease
the Diophantine exponent. This ends the proof.
This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3098

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

Proof of Theorem 1.2. The result follows directly from Propositions ABL and 4.3.

4.2. Proof of Theorem 1.3. In order to prove Theorem 1.3, we ﬁrst introduce
a useful and natural equivalence relation on the set of internal conﬁgurations of apushdown automaton. This equivalence relation is closely related to the classical
Myhill-Nerode relation used in formal language theory. Roughly, we think of two
conﬁgurations as being equivalent if, starting from each conﬁguration, there is no
way to distinguish them by feeding the machine with arbitrary inputs.
Let us introduce some notation. An internal conﬁguration of a k-pushdown
automaton M := (Q, Σk , Γ, δ, q0 , Δ, τ ) is a pair C := (q, S) ∈ Q × Γ∗ where q
denotes the state of the ﬁnite control and S denotes the word on the stack. Given
an input word w, CM (w), or C(w) for short if there is no risk of confusion, denotes
the internal conﬁguration reached by the machine M when it is started from theinitial conﬁguration and fed with the input w, that is, C(w) := δ(q0 , #, w). By
the way, τ (C(w)) denotes the corresponding output symbol produced by M. We
also use the classical notation C w C  to express that starting from the internal
conﬁguration C and reading the input word w, the machine enters into the internal
conﬁguration C  , that is, when C  = δ(C, w). When the input alphabet is Σk andn is a natural number, we simply write C(n) instead of C(nk ).
Deﬁnition 4.5. Let M be a k-pushdown automaton. Given two conﬁgurations
C1 and C2 of M, we say that C1 and C2 are equivalent, and we write C1 ∼ C2 if,for every input word w ∈ Σ∗k , one has τ (δ(C1 , w)) = τ (δ(C2 , w)).
It is obvious that ∼ is an equivalence relation. We are now ready to state thefollowing simple but key result.
Proposition 4.6. Let ξ be a real number generated by a k-pushdown automaton.
If there exist two distinct positive integers n and n such that C(n) ∼ C(n ), then
ξ is either rational or transcendental.
Proof. Let ξ be a real number whose base-b expansion can be generated by a kpushdown automaton M. Let a := (an )n≥0 be the output sequence of M, so that
{ξ}b = 0.a1 a2 · · · . Let us assume that there exist two positive integers n and n ,n < n , such that C(n) ∼ C(n ). Set wn := nk and wn := n k . By deﬁnition of
the equivalence relation, one hasa[wn w]k = a[wn w]kfor every word w ∈ Σ∗k . Given a positive integer , we obtain in particular thefollowing equalities:∀i ∈ [0, k − 1], ak n+i = ak n +i .

(4.5)

Set U := a1 a2 · · · ak n−1 and V := ak n ak n+1 · · · ak n −1 . We thus deduce from
(4.5) that the word
1+1/(n −n)U V= a1 a2 · · · ak n−1 ak n ak n+1 · · · ak n −1 ak n · · · ak n+k −1

is a preﬁx of a. Furthermore, one has
1+1/(n −n)|U V

|/|U V | = 1 +1n − 1/k

≥1+

1
·
n

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3099

Since the exponent 1 + 1/n does not depend on , this shows thatdio(a) ≥ 1 + 1/n > 1 .
Then Proposition ABL implies that ξ is either rational or transcendental, which
ends the proof.
With this proposition in hand, we observe that Theorem AB becomes obvious.
Proof of Theorem AB. Indeed, a ﬁnite k-automaton can be seen as a k-pushdown
automaton with empty stack alphabet (transitions only depend on the state anddo not act on the stack), so a conﬁguration is just given by the state of the ﬁnite
control, and the empty stack.
Since there are only a ﬁnite number of states, a ﬁnite automaton has only a ﬁnite
number of diﬀerent possible conﬁgurations. By the pigeonhole principle, there thus
exist two distinct positive integers n and n such that C(n) = C(n ). Then the
proof follows from Proposition 4.6.

We are now ready to prove Theorem 1.3. As mentioned to the authors by thereferee, the argument in the following proof is similar to the one given in the proofof Theorem 4.7.4 in [44].
Proof of Theorem 1.3. Let ξ be a real number that can be generated by a kpushdown automaton, say M := (Q, Σk , Γ, δ, q0 , Δ, τ ). Given an input word w ∈Σ∗k , we let qw denote the state reached by M when starting from its initial conﬁguration and reading the input w. We also let S(w) ∈ Γ∗ denote the corresponding
contents of the stack of M and H(w) denote the corresponding stack height, thatis, the length of the word S(w). With this notation, we obtain that starting fromthe initial conﬁguration (q0 , #) and reading the input w, M reaches the internal
conﬁguration (qw , S(w)), that is, (q0 , #) w (qw , S(w)).
For every positive integer m, we consider the set
Hm := {w ∈ Rk : H(w) ≤ m} .
We distinguish two cases.
(i) Let us ﬁrst assume that there exists a positive integer m such that Hm isinﬁnite. Note that for all w ∈ Hm , the conﬁguration C(w) := (qw , S(w)) belongs
to the ﬁnite set Q × Γ≤m , where Γ≤m denotes the set of words of length at most mdeﬁned over Γ. Since Hm is inﬁnite, the pigeonhole principle ensures the existence of
two distinct words w and w in Hm such that C(w) = C(w ). Setting n := [w]k andn := [w ]k , we obtain that n = n and C(n) = C(n ). In particular, C(n) ∼ C(n ).
Then Proposition 4.6 applies, which concludes the proof in this case.
(ii) We now turn to the case where all the sets Hm are ﬁnite. For every m ≥ 1, we
can thus pick a word vm in Hm with maximal length. Note that since Hm ⊂ Hm+1 ,we have |vm | ≤ |vm+1 |. Furthermore, one has
Rk =

∞


Hm ,

m=1

which implies that the set {vm : m ≥ 1} is inﬁnite.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3100

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

As discussed in Remark 2.13, we can assume without loss of generality that all-moves of M decrease the stack height. Furthermore, recall that all possible moves are performed after reading the last symbol of a given input. This leads to thefollowing alternative. For every internal conﬁguration (qw , S(w)) with H(w) = 0,each time a new input symbol a is consumed:• either the stack height is decreased, which means that H(wa) < H(w), and,moreover, S(wa) is a preﬁx of S(w),• or only the topmost symbol of the stack has been modiﬁed, which meansthat there exist two words X, Y ∈ Γ∗ and a letter z ∈ Γ such that S(w) =Xz while S(wa) = XY .
The deﬁnition of vm ensures that
(4.6)

∀w ∈ Σ∗k ,H(vm ) < H(vm w) .

Furthermore, if m is large enough, we have that |vm | > |v1 |, so that H(vm ) > 1.
For such m, let us decompose the stack word S(vm ) asS(vm ) = Xm zm ,where zm ∈ Γ is the topmost stack symbol. Inequality (4.6) implies that for allw ∈ Σ∗k , the word Xm is a preﬁx of the stack word S(vm w). In other words, thepart of the stack corresponding to the word Xm will never be modiﬁed or even read
during the computation (qvm , S(vm )) w (qvm w , S(vm w)). This means precisely that(qvm , S(vm )) ∼ (qvm , zm ) .
Note that (qvm , zm ) ∈ Q × Γ, which is a ﬁnite set, while we already observedthat {vm : m ≥ 1} is inﬁnite. The pigeonhole principle thus implies the existenceof two distinct integers m and m such that vm = vm and C(vm ) ∼ C(vm ).
Setting n := [vm ]k and n := [vm ]k , we get that C(n) ∼ C(n ) and n = n . Then
Proposition 4.6 applies, which ends the proof.

5. Some related models of computations:
Tag machines and stack machines
In this section, we complete our study by discussing diﬀerent types of machines.
We ﬁrst consider the tag machine that was originally introduced by Cobham [26]and we prove that Theorem 1.2 is equivalent to Cobham’s second claim. Then we
introduce a general model of computation called a multistack machine and we show
how Theorem 1.3 allows us to solve the Hartmanis–Stearns problem for this classof machines.
5.1. Tag machine. In [26], Cobham originally investigated a model of computation, called a tag machine, whose outputs turn out to be precisely the morphic
sequences deﬁned in Section 2.2. Here we describe this model and the associatednotion of dilation factor, and prove the equivalence between sequences produced bya tag machine with dilation factor larger than one and sequences generated by amorphism with exponential growth. This shows that Theorem 1.2 is equivalent toCobham’s second claim, as claimed in the introduction.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3101

A tag machine is a two-tape enumerator that can be described as follows. In
internal structure, a tag machine T (see Figure 5.1) has• a ﬁnite state control,• a working tape on which operate a read-only head R and a write-only headW.
In external structure, M has• an output tape on which operates a write-only head W and from whichnothing can be erased.
Working tapea11111111
00000000
00000000
11111111σ(a)00000000
11111111
00000000
11111111

R

W

Q
Finite controlWϕ(a)Output tapeFigure 5.1. A tag machine.
Let us brieﬂy describe how a tag machine operates. The ﬁnite state control ofT contains the following basic information:• a ﬁnite set of symbols A together with a special starting symbol a0 ,• for every symbol a ∈ A, a (possibly empty) ﬁnite word σ(a) over A,• for every symbol a ∈ A, a symbol ϕ(a) in another ﬁnite set of symbols B.
When the computation starts, R and W are both positioned on the leftmost
square of the blank working tape and W proceeds by writing the word σ(a0 ), one
symbol per square. Then both heads R and W move one square right, R scans the
symbol written in the corresponding square, say a, and W proceeds by writing theword σ(a). Again, both heads move one square to the right and the process keeps
on forever unless R and W reach the same square of the working tape, in whichcase the machine stops. Meanwhile, each time R reads a symbol a on the working
tape, W writes the symbol ϕ(a) on the output tape and moves one square right.
Each symbol written on the output tape is thus irrevocable and cannot be erased
in the process of computation. The output sequence produced by T is the sequenceof symbols written on its output tape.
Using this description [26], Cobham extracts the following usual deﬁnition of atag machine in terms of morphisms which conﬁrms that output of tag machines
and morphic sequences are the same.
Deﬁnition 5.1. A tag machine is a 5-tuple T := (A, σ, a, B, ϕ) where• A is a ﬁnite set of symbols called the internal alphabet,• a is an element of A called the starting symbol,• σ is a morphism of A∗ prolongable on a,• B is a ﬁnite set of symbols called the external alphabet.,• ϕ is a letter-to-letter morphism from A to B.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3102

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

The output sequence of T is the morphic sequence ϕ(σ ω (a)). A tag machine
is said to be uniform (resp., k-uniform) when the morphism σ has the additional
property to be uniform (resp., k-uniform).
In [26], Cobham also introduced the following interesting quantity which measures the rate of production of symbols by a tag machine.
Deﬁnition 5.2. The (minimum) dilation factor of a tag machine T is deﬁned asW(n),nwhere W(n) denotes the position of the write-only head W of T when the read-only
head R occupies the nth square of the working tape.
d(T ) := lim infn→∞Remark 5.3. It follows from Deﬁnition 5.1 that W(n) = |σ(u1 u2 · · · un )|, whereu1 u2 · · · un is the preﬁx of length n of the inﬁnite word σ ω (a).
It is easy to see that uniform tag machines, or equivalently ﬁnite automata usedas transducers (see Section 2.2), all have dilation factor at least two. As alreadymentioned, Cobham claimed that the base-b expansion of an algebraic irrational
number cannot be generated by a tag machine with dilation factor larger thanone. This result will immediately follow from Theorem 1.2 once we have proved
Proposition 5.4 below. It is stated without proof by Cobham in [26].
Proposition 5.4. Let T := (A, σ, a, B, ϕ) be a tag machine. Then the following
statements are equivalent:(i) d(T ) > 1.
(ii) The spectral radius of Mσ is larger than one.
Proof. Let us ﬁrst prove that (i) implies (ii). Since d(T ) > 1, Remark 5.3 ensuresthe existence of a positive real number ε such that
W(|σ n (a)|)|σ n+1 (a)|=>1+ε|σ n (a)||σ n (a)|for every n suﬃciently large. This implies that there exists a positive real number
c such that
|σ n (a)| > c(1 + ε)nfor every positive integer n. By Lemma 4.2, we obtain that θ, the spectral radiusof Mσ , must satisfy θ ≥ 1 + ε > 1.
Let us now prove that (ii) implies (i). Let θ > 1 denote the spectral radiusof Mσ . We argue by contradiction assuming that d(T ) = 1. Let u := σ ω (a). By
Lemma 4.2, there exist a non-negative integer , and two positive real numbers c1
and c2 such that
(5.1)

c1 n θ n < |σ n (a)| < c2 n θ n

for every positive integer n. Set C := Mσ ∞ . Let ε be a positive real number andlet m be a positive integer such thatθ m > C(1 + ε)c2 /c1 .
We then infer from (5.1) that
|σ m+n (a)| > c1 (m + n) θ m+n > θ m c1 n θ n > C(1 + ε)c2 n θ nThis is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3103

and thus|σ m+n (a)| > C(1 + ε)|σ n (a)|for every positive integer n. Let N be a positive integer and let u1 u2 · · · uN denotethe preﬁx of length N of u. Let n be the largest integer such that σ n (a) is a preﬁx
of u1 u2 · · · uN . It thus follows that|σ m (u1 · · · uN )| ≥ |σ m (σ n (a))| = |σ m+n (a)| > C(1 + ε)|σ n (a)| .
Since the deﬁnition of n ensures that |σ n (a)| > N/C, we have|σ m (u1 u2 · · · uN )| > (1 + ε)N .

(5.2)

On the other hand, for every δ > 0 there exists a positive integer N such that:|σ(u1 u2 · · · uN )|< 1+δ,
N
since by assumption d(T ) = 1. Let V be the ﬁnite word deﬁned by the relation
σ(u1 u2 · · · uN ) = u1 u2 · · · uN V . Thus |V | < δN . Now it is easy to see thatσ m (u1 u2 · · · uN ) = u1 u2 · · · uN V σ(V ) · · · σ m−1 (V ) ,which implies that|σ m (u1 u2 · · · uN )| < N + δN + CδN + · · · + C m−1 δN .
Choosing δ < ε(C − 1)/(C m − 1), we get that |σ m (u1 u2 · · · uN )| < (1 + ε)N , which
contradicts (5.2). This ends the proof.

5.2. The Hartmanis-Stearns problem for multistack machines. In this section, we discuss how our main result allows us to revisit the Hartmanis–Stearns
problem as follows. Instead of a time constraint, we impose a restriction based on
the way the memory may be stored by Turing machines. We consider a classicalmodel of computation called a multistack machine. It corresponds to a version of
the deterministic Turing machine where the memory is organized as stacks. It is
as general as the Turing machine if one allows two or more stacks. Furthermore
the one-stack machine turns out to be equivalent to the deterministic pushdown
automaton, while a zero-stack machine is just a ﬁnite automaton (a machine witha strictly ﬁnite memory only stored in the ﬁnite state control).
For a formal deﬁnition of Turing machines the reader is referred to any of theclassical references such as [31, 36, 45]. We will content ourself with the following
informal deﬁnition of a multistack machine. A multistack machine (see Figure 5.2)
is a one-way multitape deterministic Turing machine in which the memory is organized as stacks. Used as a transducer, it can be divided into three parts:• the input tape, on which there is a read-only head which cannot go to theleft (one-way machine),• the internal part, which consists of a ﬁnite control and working tapes organized as stacks (the head of each working tape is always located on therightmost non-blank symbol so that the tape can be thought of as a stackwith a head on the topmost symbol),• the output tape on which there is a write-only head and from which nothingcan be erased.
Let us brieﬂy describe how such a machine operates. A move on a multistackmachine is based on the current state of the ﬁnite control, the input symbol read,This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3104

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

Finite control

w1 w2 w3 w4 w5Input taper1 r2 r3 r4 r5 r6Q

s1 s2 s3 s4 s5 s6 s7
t1 t2 t3 t4
Working stacksa(w)Output tapeFigure 5.2. A one-way stack machine.
and the top stack symbol on each of the stacks, and involves the following actions:• for each stack, replacing the top symbol with a (possibly empty) string ofstack symbols;• moving the head of the input tape to the right;• changing the ﬁnite state control to a new state.
Remark 5.5. Again, to make the machine deterministic, a move is uniquely determined by the knowledge of the input symbol read, the state of the ﬁnite control,
and the top symbol of each stack. As for pushdown automata, a multistack machine
can also possibly perform an -move: a move for which the head of the input tapedoes not move. The possibility of such a move depends only on the current state of
the ﬁnite control and the top stack symbol on each of the stacks. Also, a multistackmachine is not allowed to stop its computation in a state from which an -move ispossible.
After reading an input word w, a multistack machine M produces an output
symbol a(w) that belongs to a ﬁnite output alphabet. The symbol a(w) depends
only on the state of the ﬁnite control and the top symbol of each stack. Given an
integer k ≥ 2, a k-multistack machine is a multistack machine that takes as input
the base-k expansion of an integer, that is, for which the input alphabet is Σk . In
that case, the sequence (a(nk ))n≥0 is called the output sequence produced by M.
With these deﬁnitions, a deterministic k-pushdown automaton is nothing else thana k-multistack machine with a single stack. One can now deﬁne the class of real
numbers generated by multistack machines as follows.
Deﬁnition 5.6. A real number ξ can be generated by a k-multistack machine M
if, for some integer b ≥ 2, one has {ξ}b = 0.a1 a2 · · · , where (an )n≥0 corresponds
to the output sequence produced by M. A real number can be generated by amultistack machine if it can be generated by a k-multistack machine for some k.
Theorem 1.3 (resp., Theorem AB) may now be rephrased as follows: No algebraic irrational can be generated by a one-stack (resp., by a zero-stack ) machine.
Incidentally, this result turns out to provide a complete picture concerning theHartmanis-Stearns problem for multistack machines. Indeed, since the two-stackmachine has the same power as the general Turing machine, any computable number(and in particular any algebraic number) can be generated by a two-stack machine.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3105

5.3. Beyond pushdown automata. We stress now that the equivalence relation∼ given in Deﬁnition 4.5 and the associated Proposition 4.6 can be naturally extended to more general models of computation. For a multistack machine and moregenerally for a multitape Turing machine, an internal conﬁguration is determinedby the state of the ﬁnite control and the complete knowledge of all the working
tapes (that is, the word written on each tape). To use the equivalence given in Definition 4.5 and the associated Proposition 4.6 we do not need to concretely describe
how the working part of the machine is organized (stacks, tapes, or whatever). All
that we need is to work with a machine with a one-way input tape and an output
tape on which every symbol written is irrevocable. We refer to these machines as
one-way transducer-like machines. When fed with a word, such a machine reads itwith a one-way reading head, and outputs a single letter on its output tape.
Let k ≥ 2 be an integer. A one-way transducer-like k-machine is deﬁned as a
6-tuple M := (Σk , C, δ, C0 , Δ, τ ) where• Σk := {0, 1, . . . , k − 1} is called the alphabet of input symbols,• C is a countable set called the set of conﬁgurations,• δ : C × Σk → C is called the transition function,• C0 ∈ C is called the initial conﬁguration,• Δ is a ﬁnite set called the alphabet of output symbols,• τ : C → Δ is called the output function.
Note that we assume that the machine is complete, that is, δ is deﬁned on allof C × Σk . With this condition, the transition function can be extended to Σ∗k by
setting, for every w ∈ Σ∗k and i ∈ Σk , δ(C, wi) = δ(δ(C, w), i).
Deﬁnition 5.7. Let M := (Σk , C, δ, C0 , Δ, τ ) be a one-way transducer-like kmachine. The output sequence produced by M is the sequence (τ (C(n)))n≥0 where
C(n) := δ(C0 , nk ) is the conﬁguration reached by M after reading the input word
nk .
Remark 5.8. Without any further restriction, one-way transducer-like k-machines
can output any sequence (an )n≥0 with values in a ﬁnite alphabet. This comes fromthe fact that the output function τ can be any function from C to Δ. In practice,
the value of the output functions τ (C) depends only on some ﬁnite amount of
information associated with the conﬁguration C, for instance, the current state
for a ﬁnite automaton, the top symbol of the stack and the current state for apushdown automaton, the top symbol of each stack and the current state for a
multistack machine, etc.
We deﬁne now an equivalence relation over the set of conﬁgurations of a one-way
transducer-like k-machine just as in Deﬁnition 4.5.
Deﬁnition 5.9. Let M be a one-way transducer-like k-machine. Given two conﬁgurations C1 and C2 in C, we say that C1 and C2 are equivalent, and we write
C1 ∼ C2 if, for every input word w ∈ Σ∗k , τ (δ(C1 , w)) = τ (δ(C2 , w)).
Deﬁnition 5.10. A real number ξ can be generated by a one-way transducerlike machine if there exist two integers k and b at least equal to 2, and a oneway transducer-like k-machine M, such that {ξ}b = 0.a1 a2 · · · , where (an )n≥0
corresponds to the output sequence produced by M.
We then have the following proposition, which can be proved in exactly the same
way as Proposition 4.6.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3106

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

Proposition 5.11. Let ξ be a real number generated by a one-way transducer-likemachine. If there exist two distinct positive integers n and n such that C(n) ∼C(n ), then ξ is either rational or transcendental.
This general result provides a method to prove the transcendence of real numbers
which can be generated by machines more powerful than a k-pushdown automaton.
For instance, it implies the transcendence of the ternary number
ξ3 := 0.110 120 110 010 110 100 101 100 110 100 110 010 110 011 010 010 112 · · ·whose nth ternary digit is equal to 2 if the binary expansion of n is of the form
1j 0j 1j , for some j ∈ N∗ , to 1 if the binary expansion of n has an odd number of occurrences of ones, and to 0 otherwise. This number cannot be generated by a k-pushdown automaton because the set of words of the form 1j 0j 1j forsome j ∈ N∗ is not a context-free language. In particular, ξ3 is irrational. However, ξ3 can be generated by a one-way transducer-like 2-machine M. This machine is obtained as the synchronisation product of the linearly bounded one-way
two-stack deterministic Turing machine recognizing the context sensitive language{1j 0j 1j , j ∈ N} and the Thue-Morse automaton. We give now a precise deﬁnition.
The machine M has a ﬁnite control given by the set Q = {i, q, r, s, t} × {0, 1}
and two stacks with a single stack symbol X. For convenience, the set of stack
conﬁgurations {X}∗ × {X}∗ is identiﬁed with N2 as follows. The stack conﬁguration (X j , X k ) is simply denoted by (j, k). The set of conﬁgurations of M isthen deﬁned by C = Q × {(j, k) ∈ N2 : j ≤ k}. The initial conﬁguration is
C0 = (i, 0, 0, 0). The transition function δ : C × Σ2 → C is deﬁned as follows. We
set δ((i, 0, 0, 0), 1) = (q, 1, 1, 1). For all (e, j, k) ∈ {0, 1} × {(j, k) ∈ N2 : j ≤ k}, wesetδ((q, e, j, j), 1) = (q, 1 − e, j + 1, j + 1), δ((r, e, 0, k), 0) = (t, e, 0, k),δ((s, e, 0, 0), 1) = (t, 1 − e, 0, 0),δ((s, e, 0, k), 0) = (t, e, 0, k),δ((t, e, j, k), 1) = (t, 1 − e, j, k),δ((t, e, j, k), 0) = (t, e, j, k),and, if moreover j and k are positive, we setδ((q, e, j, j), 0) = (r, e, j − 1, j),δ((r, e, j, k), 0) = (r, e, j − 1, k),δ((r, e, j, k), 1) = (t, 1 − e, j, k),δ((r, e, 0, k), 1) = (s, 1 − e, 0, k − 1),δ((s, e, 0, k), 1) = (s, 1 − e, 0, k − 1) .
Note that we have just deﬁned δ on C  × Σ2 , where C  is the set of all conﬁgurations
that can be reached from the initial conﬁguration, which is of course enough forour purpose. The alphabet of output symbols is Δ = Σ3 . The output function
τ : C → Δ is deﬁned by: τ (x, 1, j, k) = 1 if x ∈ {i, q, r, s, t} and (j, k) ∈ {(j, k) ∈N2 : j ≤ k}, τ (s, 0, 0, 0) = 2, and τ (x, 0, j, k) = 0 if (x, j, k) = (s, 0, 0).
The machine M works as follows. Given a control state (x, e) with x ∈ {i, q, r, s, t}
and e ∈ {0, 1}, the “e-part” gives the parity of the number of ones already read by
the machine, while the “x-part” of the control state and both stacks are devoted
to the recognition of the natural numbers whose binary expansion is of the form
1j 0j 1j . More precisely, we have that• in state (q, e) with stacks (j, j), the machine has read a preﬁx 1j ,• in state (r, e) with stacks (j, k), the machine has read a preﬁx 1k 0k−j ,• in state (s, e) with stacks (0, k), the machine has read a preﬁx 1j 0j 1j−k ,• in state (t, e), the machine has read a word which is not a preﬁx of thewords 1j 0j 1j for any j ∈ N∗ .

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3107

From the deﬁnition of M, it is easy to check that both conﬁgurations C(10) andC(20) are equal to (t, 0, 0, 0). In particular, these two conﬁgurations are equivalent,and it follows from Proposition 5.11 that ξ3 is a transcendental number.
6. Concluding remarks
We end this paper with several comments concerning factor complexity, transcendence measures, and continued fractions, and also provide possible directions
for further research.
6.1. Links with subword complexity. Another interesting way to tackle problems concerned with the expansions of classical constants in integer bases is toconsider the subword complexity (also known as factor complexity) of real numbers.
Let ξ be a real number, 0 ≤ ξ < 1, and let b ≥ 2 be a positive integer. Let
a := (an )n≥1 ∈ ΣNb denote its base-b expansion. The complexity function of ξ withrespect to the base b is the function that associates with each positive integer n thepositive integerp(ξ, b, n) := Card{(aj , aj+1 , . . . , aj+n−1 ), j ≥ 1}.
When ξ does not belong to [0, 1), we just set p(ξ, b, n) := p({ξ}, b, n).
To obtain lower bounds for the complexity of classical mathematical constantsremains a famous challenging problem. In this direction, the main result concerning
algebraic numbers was obtained by Bugeaud and the ﬁrst author [3], who provedthatp(ξ, b, n)= +∞n
for all algebraic irrational numbers ξ and all integers b ≥ 2. This lower boundimplies Theorem AB, for it is well known that a real number generated by a ﬁnite
automaton has subword complexity O(n) [27]. We stress that the situation is really
diﬀerent with pushdown automata and tag machines. Indeed, for every positive
integer d, there exist pushdown automata whose output sequence has subword
complexity growing at least like nd [38], while tag machines can output sequenceswith quadratic complexity (see, for instance, [40]). In particular, Theorems 1.2
and 1.3 do not follow from (6.1). The referee informs the authors that the studyof the complexity of sequences related to pushdown automata and context-freelanguages began with the work of Hamm on quasicontext-free sequences [29]. We
now illustrate this diﬀerence by providing lower bounds for the complexity of thetwo numbers ξ1 and ξ2 deﬁned in Sections 2.2 and 2.3.
(6.1)

lim

n→∞

6.1.1. Estimate for p(ξ1 , 3, n). It follows from the deﬁnition of the number ξ1 thatits ternary expansion is the ﬁxed point of the morphism μ deﬁned by μ(0) = 021,
μ(1) = 012, μ(2) = 2. We note that the letter 2 has clearly bounded growth(|μn (2)| = 1 for all n ≥ 0) and that μω (0) contains arbitrarily large blocks ofconsecutive occurrences of the letter 2. Then, a classical result of Pansiot [40]implies that the complexity of the inﬁnite word μω (0) is quadratic. In other words,
one hasc1 n2 < p(ξ1 , 3, n) < c2 n2
for some positive real numbers c1 and c2 and for every natural number n.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3108

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

6.1.2. Estimate for p(ξ2 , 2, n). Recall that the binary number ξ2 is deﬁned as follows: its nth binary digit is 1 if the diﬀerence between the number of occurrencesof the digits 0 and 1 in the binary expansion of n is at most 1, and is 0 otherwise.
We outline a proof of the fact thatc1 n log2 n < p(ξ2 , 2, n) < n log2 n
for some positive real numbers c1 and c2 , and for every positive integer n. We canﬁrst infer from [33] that p(ξ2 , 2, n) = O(n log2 n), for this sequence is generated bya pushdown automaton with only one ordinary stack symbol. In order to ﬁnd alower bound for p(ξ2 , 2, n), we describe a tag machine-like process (over an inﬁnite
alphabet) generating the binary expansion of ξ2 . We ﬁrst notice that anotherway to understand the action of the 2-PDA A in Figure 2.3 that generates thebinary expansion of ξ2 is to unfold it. This representation, given in Figure 6.1,
corresponds to the transition graph of A. States in this graph are given by all
possible conﬁgurations, and transitions between conﬁgurations are just labelledby the input digits 0 or 1. In Figure 6.1, the notation qX n means that, in thisconﬁguration, A is in state q and the content of the stack is XX · · · X (n times).

q1 #
1

0

1
0

q1 X

1
0

q1 X 2

1
0

q1 X 3

10

q1 X 4

1
0

q1 X 5

1

...

0

q0 #
1

0

q−1 #

0
1

q−1 X

0
1

q−1 X 201

q−1 X 301

q−1 X 401

q−1 X 50...

1

Figure 6.1. The transition graph of A.
In Figure 6.2, states of the transition graph have been renamed as follows. Conﬁgurations are replaced with integers, where reading a 1 in state n leads to a moveto state n + 1 and reading a 0 in state n leads to a move to state n − 1. We easily
see that the output state is just the diﬀerence between the number of 1’s and 0’s
in the input word. Thus the nth binary digit of ξ2 is equal to 1 if and only if thereading of the binary expansion of n by this inﬁnite automaton ends in one of thethree states labelled by 0, −1 and 1.

1/1
1

0

1

2/0

0

1

3/0

0

1

4/0

0

1

5/0

0

1

6/0

0

1

...

0

0/1
1

0

−1/1

0
1

−2/0

0
1

−3/0

0
1

−4/0

0
1

−5/0

0
1

−6/0

0

...

1

Figure 6.2. Relabelling of the transition graph of A.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS
0

3109

1

The action of 0 and 1 can be summarized by n −→ n − 1 and n −→ n + 1. This
leads to a tag machine-like process over an inﬁnite alphabet T := (A, σ, s, B, ϕ) for
generating the expansion of ξ2 . The starting symbol is s, A := Z ∪ {s}, σ is deﬁnedby σ(s) = s1 and σ(n) = (n − 1)(n + 1), B := {0, 1}, ϕ(−1) = ϕ(0) = ϕ(1) =ϕ(s) = 1, and ϕ(e) = 0 if e ∈/ {s, −1, 0, 1}. Then we have ξ2 2 = a0 .a1 a2 · · · ,where (an )n≥0 = ϕ(σ ω (s)) andσ ω (s) = s 1 0 2 (−1) 1 1 3 (−2) 0 0 2 0 2 2 4 (−3) (−1) (−1) 1 (−1) 1 1 3 (−1) 1 · · ·is the unique ﬁxed point of the morphism σ. The strategy consists now in ﬁnding
suﬃciently many diﬀerent right special factors, that is, factors w of ϕ(σ ω (s)) for
which both factors w0 and w1 also occur in ϕ(σ ω (s)). We let r > 2 and n be twonatural numbers with 2r ≤ n < 2r+1 . Arguing as in [32, Lemma 1.13], one canactually show that, for every pair(p, q) ∈ E := {(p, q) ∈ N2 : 2 ≤ p ≤ q ≤ r − 1} ,both words
A := ϕ(σ r (r − 2p − 2)σ r (r − 2p)σ r (r − 2q))
and
B := ϕ(σ r (r − 2p − 2)σ r (r − 2p)σ r (−r − 2))
occur in ϕ(σ ω (s)) and they have the same factor of length n, say w(p, q), occurring
at index 2r+1 + 2q − n − 1. That is, w(p, q) occurs just after the preﬁx of length2r+1 + 2q − n − 2 in both A and B. In the word A the factor w(p, q) is followed by
a 1, while in the word B it is followed by a 0. Thus w(p, q) is a right special factor.
It can also be extracted from [32, Lemma 1.13] that the map (p, q) → w(p, q) is
injective on E. This ensures the existence of at least (r − 2)(r − 1)/2 distinct rightspecial factors of length n in ϕ(σ ω (s)). Then it follows thatp(ξ2 , 2, n + 1) − p(ξ2 , 2, n) ≥(r − 2)(r − 1),2from which one easily deduces the lower boundp(ξ2 , 2, n) ≥ cn log2 n
for some positive real number c, and for every positive integer n.
6.2. Quantitative aspects. Here we discuss some problems related to the quantitative aspects of our results.
6.2.1. The number theory side: Transcendence measures. A real number ξ is transcendental if |P (ξ)| > 0 for all non-zero integer polynomials P . A transcendence
measure for ξ consists in a lower bound on |P (ξ)|, thus reﬁning the transcendence
statement. In general, one looks for a non-trivial function f satisfying|P (ξ)| > f (H, d)for all integer polynomials of degree at most d and height at most H. Here, H(P )stands for the naı̈ve height of the polynomial P , that is, the maximum of the absolute values of its coeﬃcients. The degree and the height of an integer polynomial
P allow us to take into account the complexity of P . Here we will use the followingclassiﬁcation of real numbers deﬁned by Mahler [35] in 1932. For every integerd ≥ 1 and every real number ξ, we let wd (ξ) denote the supremum of the exponents
w for which
0 < |P (ξ)| < H(P )−w

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3110

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

has inﬁnitely many solutions in integer polynomials P of degree at most d. Further,
we set w(ξ) := lim supd→∞ (wd (ξ)/d) and, according to Mahler [35], we say that ξ
is an
A-number if w(ξ) = 0;
S-number if 0 < w(ξ) < ∞;T -number if w(ξ) = ∞ and wd (ξ) < ∞ for any integer d ≥ 1;
U -number if w(ξ) = ∞ and wd (ξ) = ∞ for some integer d ≥ 1.
An important feature of this classiﬁcation is that two transcendental real numbersthat belong to diﬀerent classes are algebraically independent. The A-numbers are
precisely the algebraic numbers and, in the sense of the Lebesgue measure, almost
all numbers are S-numbers.
A Liouville number is a real number ξ such that for any positive real number ρ
the inequality
1
p
< ρ
ξ−
q
q
has at least one solution (p, q) ∈ Z2 with q > 1. Thus ξ is a Liouville number if
and only if w1 (ξ) = +∞. Liouville numbers are a subclass of U -numbers.
Let ξ be an irrational real number deﬁned through its base-b expansion, say
{ξ}b := 0.a1 a2 · · · . Let us assume that the base-b expansion of ξ can be generated
either by a pushdown automaton or by a tag machine with dilation factor larger
than one. As recalled in Proposition ABL (Section 3), the key point for provingthat ξ is transcendental is to show that dio(a) > 1, where a := a1 a2 · · · . This
amounts to ﬁnding two sequences of ﬁnite words (Un )n≥0 and (Vn )n≥0 , a sequenceof rational numbers αn , and a real number δ > 0 such that the word Un Vnαn is a
preﬁx of a, the length of the word Un Vnαn increases, and(6.2)|Un Vnαn |≥ 1+δ.
|Un Vn |A look at the proofs of Theorems 1.2 and 1.3 show that one actually has, in bothcases, the following extra property. There exists a real number M such that
(6.3)

lim supn→∞|Un+1 Vn+1 |<M.
|Un Vn |Using an approach introduced in [9] and developed in [7], one can ﬁrst deduce from
Inequalities (6.2) and (6.3) that
(6.4)

dio(a) − 1 ≤ w1 (ξ) ≤ c1 dio(a)for some real number c1 that depends only on δ and M . In particular, inequalities(6.2) and (6.3) imply that ξ is a Liouville number if and only if dio(a) is inﬁnite.
Then it is proved in [7], following a general approach introduced in [5] and basedon a quantitative version of the subspace theorem, that this extra condition leads
to transcendence measures. Indeed, taking all parameters into account, one canderive an upper bound of the type
(6.5)

wd (ξ) ≤ max{w1 (ξ), (2d)c2 (log 3d)(log log 3d) }for all positive integers d and some real number c2 that depends only on δ and M .
The constants c1 and c2 can be made eﬀective. In particular, we deduce the following result from inequalities (6.4) and (6.5).

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3111

Theorem 6.1. Let ξ be an irrational real number such that {ξ}b := 0.a1 a2 · · ·and let a := a1 a2 · · · . Let us assume that the base-b expansion of ξ can be generated
either by a pushdown automaton or by a tag machine with dilation factor larger
than one. Then one of the following holds:(i) dio(a) = +∞ and ξ is a Liouville number,(ii) dio(a) < +∞ and ξ is an S- or a T -number.
Of course, in view of Theorem 6.1, it would be interesting to prove whether or
not there exist irrational real numbers that can be generated either by a pushdown
automaton or by a tag machine, and for which dio(a) = +∞. In this direction, it isproved in [9] that dio(a) is always ﬁnite when ξ is generated by a ﬁnite automaton.
Here we add the following contribution to this problem.
Proposition 6.2. Let a := a0 a1 · · · be an aperiodic pure morphic word generated
by a morphism σ deﬁned over a ﬁnite alphabet A. Set M := max{|σ(i)| : i ∈ A}.
Then dio(a) ≤ M + 1.
Proof. By deﬁnition, there exists a letter a ∈ A such that σ is prolongable on
the letter a and σ ω (a) = a0 a1 · · · . We argue by contradiction by assuming thatdio(a) > M + 1. This assumption ensures that one can ﬁnd two ﬁnite words U and
V and a real number s > 1 such that(i) U V s is a preﬁx of a, and s is maximal with this property;(ii) |U V s |/|U V | ≥ M + 1 ;(iii) V is primitive (i.e., is non-empty and not the integral power of a shorter
word).
Note that since a is ﬁxed by σ then the word σ(U V s ) is also a preﬁx of a. By
deﬁnition of M , it follows from (ii) thatU V s = σ(U )W ,where W := V α for some conjugate V of V (i.e., V = AB and V = BA for someA, B) and α ≤ s. We stress that, since σ is prolongable on a, W and σ(V ) are nonempty words. On the other hand, σ(V ) is also a period of W since U V s = σ(U )W
is a preﬁx of σ(U V s ) = σ(U )σ(V )s for some s . Thus W has at least two periods:V and σ(V ). Furthermore, (ii) implies that|U V s−1 | ≥ M (|U | + |V |) ≥ |σ(U )| + |σ(V )|and then|W | = |U V s | − |σ(U )| ≥ |σ(V )| + |V | = |σ(V )| + |V | .
We can thus apply Fine and Wilf’s theorem (see, for instance, [12, Chapter 1]) to
the word W and we obtain that there is a word of length gcd(|V |, |σ(V )|) that is aperiod of W . But, since V is primitive, the word V is primitive too, and it follows
that gcd(|V |, |σ(V )|) = |V |. This gives that σ(V ) = V j for some positive integer j.
It follows thatσ(U V s ) = σ(U )V js = U V s−α+js
is a preﬁx of a. Now the inequality |σ(U V s )| > |U V s | gives a contradiction withthe maximality of s. This ends the proof.
This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3112

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC

6.2.2. The computer science side. Theorems AB, 1.2, and 1.3 show that someclasses of Turing machines are too limited to produce the base-b expansion of analgebraic irrational real number. Let ξ be an irrational real number that can begenerated by a k-pushdown automaton or by a tag machine with dilation factor
larger than one. Then the results of Section 6.2 could be rephrased to provide alimitation of the way ξ can be approximated by irrational algebraic numbers. In
this section, we suggest to view things from a diﬀerent angle, changing our target.
Indeed, we ﬁx an algebraic irrational real number α and a base b, and ask for how
long the base-b expansion of α can be imitated by outputs of a given class of Turingmachines.
Let us explain now how to formalize our problem. We can naturally take thenumber of states as a measure of complexity of a k-automaton. One can also deﬁne
the size of k-pushdown automata and tag machines as follows. Let us deﬁne the sizeof a k-pushdown automaton A := (Q, Σk , Γ, δ, q0 , Δ, τ ) to be |Q| + |Γ| + L, where
L is the maximal length of a word that can be added to the stack by the transition
function δ of A. Let us also deﬁne the size of a tag machine T := (A, σ, a, ϕ, B) tobe |A| + L, where L := max{|σ(i)| : i ∈ A}. Now, let us ﬁx a class M of Turingmachines among k-automata, k-pushdown automata, and tag machines. Let M bea positive integer. We stress that there are only ﬁnitely many such machines withsize at most M . Then there exists a maximal positive integer I(α, M ) for which
there exists a machine in M with size at most M whose output agrees with thebase-b expansion of α at least up to the I(α, M )th digit. We suggest the following
problem.
Problem 6.3. Let α be an algebraic irrational real number and ﬁx a class of Turingmachines among k-automata, k-pushdown automata, and tag machines. Given a
positive integer M , ﬁnd an upper bound for I(α, M ).
In the case of ﬁnite automata, we can give a ﬁrst result toward this problem.
Indeed, the subword complexity of the output a of a k-automaton with at most M
states satisﬁes p(a, n) ≤ kM 2 n (see, for instance, [12, Theorem 10.3.1]). Let d andH denote the degree and the height of α, respectively. Then the main result of [19]allows us to extract the following upper bound:2I(α, M ) ≤ max (max(log H, e)100kM 2 )8 log 4kM ,2.1 
(log d)10100 (kM 2 )11/2 log(kM 2 ).
6.3. Computational complexity of the continued fraction expansion ofalgebraic numbers. Replacing integer base expansions with continued fractions
leads to similar problems. Rational numbers all have a ﬁnite continued fraction expansion, while quadratic real numbers correspond to eventually periodic continued
fractions. In contrast, much less is known about the continued
fraction expansion√of algebraic real numbers of degree at least three such as 3 2. In this direction, an
approach based on the subspace theorem was introduced by Bugeaud and the ﬁrst
author [2]. Recently, Bugeaud [20] showed that this approach actually leads to thefollowing analogue of Proposition ABL.
Proposition B. Let ξ be a real number with ξ := [a0 , a1 , a2 , . . .] where we assume
that (an )n≥1 is a bounded sequence of positive integers. Let us assume that dio(a) >1 where a := a1 a2 · · · . Then ξ is either quadratic or transcendental.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3113

In [20], the author deduces from Proposition B that the continued fraction expansion of an algebraic real number of degree at least 3 cannot be generated by aﬁnite automaton. This provides the analogue of Theorem AB in this framework.
As a direct consequence of our results and Proposition B, we obtain the following
generalization of Bugeaud’s result corresponding to the analogue of Theorems 1.2
and 1.3.
Theorem 6.4. Let ξ be an algebraic real number of degree at least 3. Then thefollowing holds:(i) The continued fraction expansion of ξ cannot be generated by a one-stackmachine, or equivalently, by a deterministic pushdown automaton.
(ii) The continued fraction expansion of ξ cannot be generated by a tag machinewith dilation factor larger than one.
Using the approach introduced in [6] and the discussion of Section 6.2, it will also
be possible to produce transcendence measures analogous to Theorem 6.1 for real
numbers whose continued fraction expansion can be generated by a deterministic
pushdown automaton or by a tag machine with dilation factor larger than one.
7. Acknowledgments
We warmly thank the referee for the very careful reading of a previous version ofthis paper. The current presentation has strongly beneﬁted from the suggestions.
References[1] Boris Adamczewski, On the expansion of some exponential periods in an integer base, Math.
Ann. 346 (2010), no. 1, 107–116, DOI 10.1007/s00208-009-0391-z. MR2558889[2] Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. II. Continued fractions, Acta Math. 195 (2005), 1–20, DOI 10.1007/BF02588048. MR2233683[3] Boris Adamczewski and Yann Bugeaud, On the complexity of algebraic numbers. I. Expansions in integer bases, Ann. of Math. (2) 165 (2007), no. 2, 547–565, DOI 10.4007/annals.2007.165.547. MR2299740[4] Boris Adamczewski and Yann Bugeaud, Dynamics for β-shifts and Diophantine approximation, Ergodic Theory Dynam. Systems 27 (2007), no. 6, 1695–1711, DOI
10.1017/S0143385707000223. MR2371591[5] Boris Adamczewski and Yann Bugeaud, Mesures de transcendance et aspects quantitatifs
de la méthode de Thue-Siegel-Roth-Schmidt (French, with English and French summaries),
Proc. Lond. Math. Soc. (3) 101 (2010), no. 1, 1–26, DOI 10.1112/plms/pdp054. MR2661240[6] Boris Adamczewski and Yann Bugeaud, Transcendence measures for continued fractions
involving repetitive or symmetric patterns, J. Eur. Math. Soc. (JEMS) 12 (2010), no. 4,
883–914, DOI 10.4171/JEMS/218. MR2654083[7] Boris Adamczewski and Yann Bugeaud, Nombres réels de complexité sous-linéaire: mesuresd’irrationalité et de transcendance (French, with English summary), J. Reine Angew. Math.
658 (2011), 65–98, DOI 10.1515/CRELLE.2011.061. MR2831513[8] Boris Adamczewski, Yann Bugeaud, and Florian Luca, Sur la complexité des nombresalgébriques (French, with English and French summaries), C. R. Math. Acad. Sci. Paris
339 (2004), no. 1, 11–14, DOI 10.1016/j.crma.2004.04.012. MR2075225[9] Boris Adamczewski and Julien Cassaigne, Diophantine properties of real numbers
generated by ﬁnite automata, Compos. Math. 142 (2006), no. 6, 1351–1372, DOI
10.1112/S0010437X06002247. MR2278750[10] Boris Adamczewski and Colin Faverjon, Méthode de Mahler: relations linéaires, transcendance et applications aux nombres automatiques (French, with English and French summaries), Proc. Lond. Math. Soc. (3) 115 (2017), no. 1, 55–90, DOI 10.1112/plms.12038.
MR3669933

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

3114

BORIS ADAMCZEWSKI, JULIEN CASSAIGNE, AND MARION LE GONIDEC[11] J. Albert, Propriétés combinatoires et arithmétiques de certaines suites automatiques et substitutives, Thèse de Doctorat de l’Université Paris Sud, 2006.
[12] Jean-Paul Allouche and Jeﬀrey Shallit, Automatic sequences, Cambridge University Press,
Cambridge, 2003. Theory, applications, generalizations. MR1997038[13] J.-M. Autebert, Langages algébriques (French), Études et Recherches en Informatique. [Studies and Research in Computer Science], Masson, Paris, 1987. MR888601[14] Jean-Michel Autebert, Jean Berstel, and Luc Boasson, Context-free languages and pushdown automata, Handbook of formal languages, Vol. 1, Springer, Berlin, 1997, pp. 111–174.
MR1469995[15] J. Berstel and L. Boasson, Modèles de machines, Encyclopédie de l’informatique et dessystèmes d’information, pp. 987–998, Vuibert, 2006.
[16] Daniel Bertrand, Theta functions and transcendence, Ramanujan J. 1 (1997), no. 4, 339–
350, DOI 10.1023/A:1009749608672. International Symposium on Number Theory (Madras,
1996). MR1608721[17] É. Borel, Les probabilités dénombrables et leurs applications arithmétiques, Rend. Circ. Mat.
Palermo 27 (1909), 247–271.
[18] J. M. Borwein and P. B. Borwein, On the complexity of familiar functions and numbers,
SIAM Rev. 30 (1988), no. 4, 589–601, DOI 10.1137/1030134. MR967961[19] Yann Bugeaud, An explicit lower bound for the block complexity of an algebraic number, Atti Accad. Naz. Lincei Rend. Lincei Mat. Appl. 19 (2008), no. 3, 229–235, DOI
10.4171/RLM/521. MR2439519[20] Yann Bugeaud, Automatic continued fractions are transcendental or quadratic (English, withEnglish and French summaries), Ann. Sci. Éc. Norm. Supér. (4) 46 (2013), no. 6, 1005–1022,
DOI 10.24033/asens.2208. MR3134686[21] Julien Cassaigne and François Nicolas, Factor complexity, Combinatorics, automata and number theory, Encyclopedia Math. Appl., vol. 135, Cambridge Univ. Press, Cambridge, 2010,
pp. 163–247. MR2759107[22] Didier Caucal and Marion Le Gonidec, Context-free sequences, Theoretical aspects ofcomputing—ICTAC 2014, Lecture Notes in Comput. Sci., vol. 8687, Springer, Cham, 2014,
pp. 259–276, DOI 10.1007/978-3-319-10882-7 16. MR3278460[23] N. Chomsky, Three models for the description of language, IRE Trans. Information Theory
18 (1956), 113–124.
[24] A. Cobham, Functional equations for register machines, Proccedings of the Hawaii International Conference on System Sciences, Honolulu, pp. 10–13, 1968.
[25] A. Cobham, A proof of transcendence based on functional equations, RC–2041, IBM ResearchCenter, Yorktown Heights, New York, 1968.
[26] A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, IEEE Conference
Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pp. 51–60,
1968.
[27] Alan Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192, DOI
10.1007/BF01706087. MR0457011[28] Daniel Duverney, Keiji Nishioka, Kumiko Nishioka, and Iekata Shiokawa, Transcendenceof Jacobi’s theta series, Proc. Japan Acad. Ser. A Math. Sci. 72 (1996), no. 9, 202–203.
MR1434685[29] D. Hamm, Contributions to formal language theory: Fixed points, complexity, and contextfree sequences, M.Sc. Thesis, University of Waterloo, 1998.
[30] J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans. Amer.
Math. Soc. 117 (1965), 285–306, DOI 10.2307/1994208. MR170805[31] John E. Hopcroft and Jeﬀrey D. Ullman, Introduction to automata theory, languages, andcomputation, Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series
in Computer Science. MR645539[32] Marion Le Gonidec, Drunken man inﬁnite words complexity, Theor. Inform. Appl. 42 (2008),
no. 3, 599–613, DOI 10.1051/ita:2008012. MR2434037[33] Marion Le Gonidec, On the complexity of a family of k-context-free sequences, Theoret.
Comput. Sci. 414 (2012), 47–54, DOI 10.1016/j.tcs.2011.09.022. MR2896582[34] J. Liouville, Sur des classes très étendues de quantités dont la valeur n’est ni algébrique, nimême réductible à des irrationelles algébriques, C. R. Acad. Sci. Paris 18 (1844), 883–885 et
993–995.

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.

COMPUTATIONAL COMPLEXITY OF ALGEBRAIC NUMBERS

3115[35] Kurt Mahler, Zur Approximation der Exponentialfunktion und des Logarithmus. Teil II(German), J. Reine Angew. Math. 166 (1932), 137–150, DOI 10.1515/crll.1932.166.137.
MR1581303[36] Marvin L. Minsky, Computation: ﬁnite and inﬁnite machines, Prentice-Hall, Inc., Englewood
Cliﬀs, N.J., 1967. Prentice-Hall Series in Automatic Computation. MR0356580[37] Marston Morse and Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938),
no. 4, 815–866, DOI 10.2307/2371264. MR1507944[38] Yossi Moshe, On some questions regarding k-regular and k-context-free sequences, Theoret.
Comput. Sci. 400 (2008), no. 1-3, 62–69, DOI 10.1016/j.tcs.2008.02.018. MR2424342[39] Yu. V. Nesterenko, Modular functions and transcendence questions (Russian, with Russiansummary), Mat. Sb. 187 (1996), no. 9, 65–96, DOI 10.1070/SM1996v187n09ABEH000158;
English transl., Sb. Math. 187 (1996), no. 9, 1319–1348. MR1422383[40] Jean-Jacques Pansiot, Complexité des facteurs des mots inﬁnis engendrés par morphismesitérés (French, with English summary), Automata, languages and programming (Antwerp,
1984), Lecture Notes in Comput. Sci., vol. 172, Springer, Berlin, 1984, pp. 380–389, DOI
10.1007/3-540-13345-3 34. MR784265[41] Patrice Philippon, Groupes de Galois et nombres automatiques (French, with English
and French summaries), J. Lond. Math. Soc. (2) 92 (2015), no. 3, 596–614, DOI
10.1112/jlms/jdv056. MR3431652[42] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes
in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi,
C. Mauduit and A. Siegel. MR1970385[43] Martine Queﬀélec, Substitution dynamical systems—spectral analysis, 2nd ed., Lecture Notes
in Mathematics, vol. 1294, Springer-Verlag, Berlin, 2010. MR2590264[44] J. Shallit, A second course in formal languages and automata theory, Cambridge University
Press, Cambridge, 2008.
[45] M. Sipser, Introduction to the theory of computation, third edition, Wadsworth Publishing
Co. Inc., 2012.
[46] Seppo Sippu and Eljas Soisalon-Soininen, Parsing theory. Vol. I, Languages and parsing.
EATCS Monographs on Theoretical Computer Science, vol. 15, Springer-Verlag, Berlin, 1988.
MR960693[47] A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem.
A Correction, Proc. London Math. Soc. (2) 43 (1937), no. 7, 544–546, DOI 10.1112/plms/s243.6.544. MR1575661
Université Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut
Camille Jordan, F-69622 Villeurbanne Cedex, France
Email address: Boris.Adamczewski@math.cnrs.fr
CNRS, Aix-Marseille Université, Institut de Mathématiques de Marseille, case 907,
163 avenue de Luminy, 13288 Marseille Cedex 9, France
Email address: Julien.Cassaigne@math.cnrs.fr
Université de la Réunion, Laboratoire d’Informatique et de Mathématiques, Parc
technologique universitaire, 2 rue Joseph Wetzell, 97490 Sainte-Clotilde, Réunion
FranceEmail address: marion.le-gonidec@univ-reunion.fr

This is a free offprint provided to the author by the publisher. Copyright restrictions may apply.