Realtime computation and algebraic numbers

Juris Hartmanis is one of the founders of the entire field of Computational Complexity Theory. His early work with Richard Stearns was recognized by the ACM with the prestigious Turing Award in 1993. Besides his seminal results on complexity theory, he also made at least three major conjectures that have helped shape the field. One conjecture concerns an simple but appealing problem about what real numbers Turing Machines can recognize in “real time”. His other conjectures are perhaps better known, but for today’s post we will discuss this one. I like it because it is so fundamental, it is simple to state, is related to interesting mathematics, and remains wide open. I hope that we might be able to push back the curtain on this problem in the future. We will see.

Real numbers fall into two basic categories. Every real numbers is either an algebraic number or a transcendental number. The former are called algebraic since they satisfy some equation over the integers. Thus, ${\sqrt 2}$ is algebraic since it is a root of the equation ${x^{2}-2 = 0}$. The latter, the transcendental numbers, are those that are not the roots of any equation. Thus, famous examples of transcendental numbers include ${\pi}$ and ${e}$. Note, that rational numbers are contained in the category of algebraic numbers: a rational number ${\frac{p}{q}}$ satisfies the trivial equation: ${qx-p = 0}$.

Every rational number has an eventually periodic decimal expression. (Actually this works for any radix, but let’s stay with decimal today.) Thus,

$\displaystyle 0.43533333333333333\dots$

is a rational number. From a complexity point of view this means that recognizing such a number is easy. Note, for every rational number there is a finite state automata that can recognize exactly the decimal expansion of the number.

Every transcendental number is of course not eventually periodic. The curious point is that some, not all, of the transcendental numbers are also extremely easy to recognize. This was first proved in in 1844 by Joseph Liouville. He showed that a certain class of real numbers is transcendental. These numbers are now named in his honor. A Liouville number is a real number ${x}$ that can be extremely well approximated by rational numbers. More precisely, for any natural number ${n}$, there are integers ${p}$ and ${q}$ with ${q > 1}$ and such that

$\displaystyle 0 < \mid x - \frac{p}{q} \mid < \frac{1}{q^{n}}.$

His most famous example is:

$\displaystyle c = \sum_{i=0}^{\infty} 10^{-i!}.$

It easy to prove that ${c}$ is a Loiuville number, and hence is transcendental. This number is

$\displaystyle 0.1100010000000000000000010000\dots$

is known as Loiuville’s constant: he got this also named after him. The reason that these numbers are so easy to recognize is that all we need to do is count the number of ${0}$‘s between the ${1}$‘s.

The Conjecture

Hartmanis beautiful conjecture is that roughly this is all that can happen. If a number is easy to recognize, in a way to be made precise shortly, then it must be either rational or transcendental. It cannot be a proper algebraic number. This remains completely wide open.

The key is the notion of what it means to be “easy to recognize”. The formal notion is based on the notion of a real-time Turing Machine. A real number is computable in real-time if there is a multi-tape Turing machine that recognizes each digit in constant time. Thus, the ${n^{th}}$ digit is recognized at time ${O(n)}$. Note, we insist that a stronger constraint is used: the gap between generating each digit is absolutely bounded by a constant ${O(1)}$.

A Partial Result

I once worked on this problem, but got a very weak result. Since there seems to be nothing really known about the problem still I thought I would share the idea with you. Suppose that $x$ is a real number in the interval $[0,1]$. Let $L$ be the set of all prefixes of this number: thus $L$ contains exactly $x_1x_2x_3 \dots x_n$ for each $n$. Then, if a restricted Turing Machine accepted $L$, could we prove that $x$ was either rationale or transcendental?

If $L$ was accepted by a finite state automata or even a pushdown automata, then it is easy to prove that $x$ is rational. These proofs use the famous “pumping lemma” of language theory.

I also considered a much stronger type of machine called a stack automata. These machines have one tape that they can use as a stack. A stack is like a pushdown but has the additional power that the contents of the stack can be read without being popped off. Thus, a stack has a head that can go into the stack and read. However, they can only write or erase at the top of the stack. These stack machines are much more powerful then pushdown automata.

For these machines I could prove that any real number they recognize must be a rational number. The proof is not hard but relies on an old but complex generalization of the famous pumping lemma for pushdown automata. In particular it uses the Intercalation theorems for stack automata proved by William Ogden in 1969. I will not state this theorem: it is essentially the classic pumping lemma on anabolic steroids. The name “Intercalation” comes from the fact that the theorem adds strings to strings already known to be accepted by a stack automata. Google says that “intercalation” is the insertion of a leap day, week or month into some calendar years to make the calendar follow the seasons or moon phases. Don’t blame me–Ogden selected the name. By the way his paper appeared in the first annual ACM symposium on Theory of computing conference. Pretty cool.

Open Problems

Clearly, the main question is to prove or disprove the conjecture. What is the next class that can be studied after those numbers recognized by stack automata? Perhaps there is a clever algebraic number that we can construct that is easy to recognize. Or perhaps we can show that the real-time restriction forces the number to have some special property, a property that forces the number to not be properly algebraic. Either way a solution to this problem would shed light both on computation and on number theory.

1. March 9, 2009 8:24 am

cooooolest domain name)))
————————

2. March 10, 2009 2:20 am

great domain name for blog like this)))
————————

3. March 10, 2009 1:59 pm

great domain name for blog like this)))
————————

4. March 10, 2009 2:56 pm

great domain name for blog like this)))
————————

March 22, 2009 11:56 am

A related result which may be of interest concerns real numbers with a so-called “automatic” decimal expansion. In the late 60’s / early 70’s, Cobham studied the following model of computing real numbers with finite automata. Suppose we have a deterministic finite automaton M where we have associated to each state q an output t(q). Then a sequence (a_n)_{n>=0} is “k-automatic” if there is such an automaton M that, given n in base k as input, reaches state q after reading n and outputs t(q) = a_n. That is, the n-th term of the sequence is output by the automaton M when M is fed with n in base k as input. Remarkably, Adamczewski, Bugeaud, and Luca have recently proved that any real number whose decimal expansion is k-automatic is either rational or transcendental. The proof uses some deep machinery from the theory of diophantine approximation. The original proof in French is here; an English version is here.

March 22, 2009 12:28 pm

Thanks for pointing this out.