The Real Conjecture of Hartmanis

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, is algebraic since it is a root of the equation . The latter, the transcendental numbers, are those that are not the roots of any equation. Thus, famous examples of transcendental numbers include and . Note, that rational numbers are contained in the category of algebraic numbers: a rational number satisfies the trivial equation: .

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

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 that can be extremely well approximated by rational numbers. More precisely, for any natural number , there are integers and with and such that

His most famous example is:

It easy to prove that is a Loiuville number, and hence is transcendental. This number is

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 ‘s between the ‘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 digit is recognized at time . Note, we insist that a stronger constraint is used: the gap between generating each digit is absolutely bounded by a constant .

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 is a real number in the interval . Let be the set of all prefixes of this number: thus contains exactly for each . Then, if a restricted Turing Machine accepted , could we prove that was either rationale or transcendental?

If was accepted by a finite state automata or even a pushdown automata, then it is easy to prove that 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.