Mathematical effects of the Hartmanis-Stearns conjecture

David Champernowne is one of a select few to have a number named for him. His number is obtained by writing all the decimal natural numbers in sequence after the decimal point. He devised it in 1933 while an undergraduate at Cambridge University. He proved the number is normal in base 10, meaning that every sequence of digits of some length ${k}$ appears with frequency approaching ${1/10^k}$ among the first ${N}$ digits as ${N}$ grows. Not even ${\pi}$ and ${e}$ are known to be normal, in any base. His point was that a number can pass tests of randomness and yet be far from random.

Today we re-visit a beautiful conjecture of Juris Hartmanis and Richard Stearns, which connects real-time computations of Turing machines to the problem of proving that numbers like this are transcendental.

Champernowne was friends with Alan Turing at King’s College, Cambridge. Indeed one typescript copy of Turing’s famous “On computable numbers…” paper has Turing’s handwritten notes on the back for a second paper to be titled, “A note on normal numbers.”

Later in 1948 they joined forces and joined their names to create Turochamp, which is now regarded as the first design of a chess-playing program. Turochamp alas was also vaporware—rather called paperware: since no physical device could yet implement their machine instructions, they traced its execution on paper. The program beat Champernowne’s wife but lost to Alick Glennie. Perhaps the thus-humiliated wife prevailed on Champernowne to take up instead a professorship in economics, in which his magnum opus was published 50 years later, in 1998.

## What Makes a Definition “Mathematical”?

The rule for Champernowne’s number is so simple a child can do it—given infinite time. Just write a dot and the integers in sequence:

$\displaystyle C_{10} = 0.12345678910111213141516171819202122\dots$

We can imagine a classical real analyst like G.H. Hardy wrinkling his nose and asking, how would you define that in mathematics? Our friends at Wikipedia give a formula of classical pedigree:

$\displaystyle C_{10} = \sum_{n=1}^\infty \sum_{k = 10^{n-1}}^{10^n - 1} \frac{k}{10^{kn-9\sum_{k=0}^{n-1}10^k(n-k)}}.$

But a computer scientist would wonder how on earth to compute with such an expression.

Enter a child, teenage chess fan Joshua Stubbs of Pretoria, South Africa, with a “Goldilocks” solution. After some further fixing by commenters below that may have traced to a formatting issue, his formula becomes:

$\displaystyle C_{10} = \sum_{k=1}^\infty \frac{k}{10^{(k+1)\ell - (10^\ell - 1)/9}}\quad\text{where}\quad \ell = 1 + \lfloor \log_{10} k\rfloor.$

The floor function is not part of classical smooth mathematics, but it is a mainstay in discrete math, and the formula is both simpler and more clearly computational. The Hartmanis-Stearns conjecture bridges the issues here, for the purpose of proving numbers to be transcendental.

## Rationals and Algebraics and Transcendentals

A real number is algebraic if it is a root of a polynomial equation with integer coefficients, and transcendental otherwise. Algebraic numbers include rationals, which are exactly those real numbers whose expansion (in decimal or any base) is eventually periodic.

Proofs that real numbers we care about are transcendental have historically been hard. This was so with Kurt Mahler’s proof in 1937 that ${C_{10}}$ is transcendental. It employed a difficult theorem obtained in progressively stronger form by Axel Thue, Carl Siegel, Freeman Dyson, and finally Klaus Roth:

Theorem: Let ${\epsilon>0}$. If ${\alpha}$ is an irrational algebraic number, then the inequality

$\displaystyle \left| \alpha - \frac{p}{q} \right| < \frac{p}{q^{2 + \epsilon}}$

can have only a finite number of solutions where ${p,q}$ are relatively prime integers.

To illustrate the difficulty, no way of computing a bound on ${p,q}$ is known given ${\alpha}$ and ${\epsilon}$.

## The Conjecture

A Turing machine operates in real time if it reads an input and writes an output at each step. For computing ${n}$ digits of a real number the input is ${0^n}$, while the same machine can be regarded as having an infinite computation with no input. Computing a rational number needs no use of work tapes at all: just wire in the finite control the transitions that compute the finite initial part, and follow with a finite loop that outputs the periodic part over and over again. Indeed, for every rational number there is a finite state automaton that can recognize exactly the decimal expansion of the number.

Hartmanis-Stearns Conjecture (HSC): Every real number computed by a real-time multitape Turing machine is either rational or transcendental.

After almost half a century of active research by computer scientists and mathematicians this is still open. However, it has become more interesting than in 1965. By known results it suffices for the Turing machine to output a digit every ${k}$th step, for some fixed ${k \geq 1}$, and the machine may be allowed to have multiple heads on each tape.

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 are transcendental. These numbers are now named in his honor. A Liouville number is a real number ${\alpha}$ that can be extremely well approximated by rational numbers: for all ${M}$ and ${n}$ there exist integers ${p,q}$ such that

$\displaystyle \left|\alpha - \frac{p}{q}\right| < \frac{1}{Mq^n}.$

Liouville proved that every such number is either rational or transcendental. Any number such that the ${k}$th nonzero digit comes in place ${f(k)}$ where ${f}$ is super-polynomial qualifies. This criterion strikes us as hard to apply in cases that lack this kind of sparseness. It requires explicit attention to approximations, while the real-time computability condition does not.

## An Application

To invoke the HSC we must show that there is a realtime Turing machine that can output the decimal digits of Champernowne’s number. The simple idea is to have a counter ${C}$ that runs consecutively through the values ${0,1,2,3,\dots}$ and the machine simply outputs the value of the counter. There is a slight issue here: the realtime constraint forces us to write out the values of the counter high-order digit first, while we also increment the counter by ${1}$ for the next value. These two operations are in conflict with each other, and this forces us to have to be a bit clever in how we proceed. Another issue is that all this must be done on a Turing machine, not on a random access machine.

But it turns out that we only need be a tiny bit clever. Lets imagine that we have two counters that we will denote by ${T}$ and ${B}$—top and bottom. Imagine that they are stored on separate Turing tapes and that the heads are arranged as depicted below:

In this case ${T}$ is the lead counter, and its value is ${1}$ more than the counter ${B}$. The machine proceeds in the following manner: the head on ${T}$ moves left to right and outputs the value of the counter. The head on the ${B}$ counter moves right to left and adds ${2}$ to the counter’s value. That is right, it adds ${2}$. In this way the next state of the machine is:

The critical point is that now ${B}$ is the lead counter. This allows the machine to repeat the same operation with the roles of ${T}$ and ${B}$ exchanged. Clearly, this all works, and the machine can continue doing this forever.

## So What?

Okay, we just used the un-proved, and likely according to some false, HSC to “re-prove” a result of Malher. So who cares? I do. There are three reasons that seeing where the conjecture goes makes sense:

${\bullet }$ The best case possible, well perhaps, is that we reach a contradiction. If we do then the HSC is false, as many seem to believe.

${\bullet }$ Another cool case would be we can use HSC to resolve an open problem. Suppose that we could use it to prove that ${\pi + e}$ is transcendental, which is still open. This would be great. We covered new algorithms for the digits of ${\pi}$ here and here, though this still falls short of what’s needed to invoke the conjecture.

${\bullet }$ The best case we can do right now is to try and use HSC to give alternative proofs that numbers are transcendental. Our above argument for ${C_{10}}$ already shows that the conjecture must be deep.

To elaborate: since Malher’s proof relies on the deep result of Roth, this shows the power of the conjecture. If nothing else, the above simple Turing programming shows that the conjecture contains at least some part of Roth’s Theorem.

Rusins Freivalds has a nice recent paper with the same motivations and further details. It also works toward applications of HSC to other transcendental numbers, and lays out some preliminary promising results toward proving the conjecture.

## Open Problems

I wonder if it may be possible to use the Hartmanis-Stearns conjecture for “proving” that other interesting numbers are transcendental. That would be very cool. Even the above example is interesting, since it shows already the power of the conjecture.

[fixed J. Stubbs’ formula]

28 Comments leave one →
1. June 4, 2012 1:32 pm

Not to be a troll… but the goldilocks formula does not seem correct. It gives approximately 0.01234567890000000000101112131415161718192021…. Aside from the off-by-one error, it clearly is shifting things too far over when k jumps to the next power of 10. I imagine that you could replace L with a correct shift if you really wanted to, probably still involving the log function and floors.

• June 4, 2012 1:48 pm

Also, I was reading your earlier post explaining the HSC. I do not quite understand the model of a real-time Turing machine and in particular I am wondering if you have a short concrete example of a real-time Turing machine that generates/recognizes a non-rational number (e.g., Liouville’s number). I think I don’t understand the model of exactly what input/output/working tapes the real-time machine should have. Thanks if you are able to clarify!

• June 4, 2012 2:35 pm

Thanks. Is this a problem with the original version of the formula on the Wikipedia link? I made a substitution to simplify it. Thanks for checking it. The real-time TM model here does not use an input tape, as it is carrying out a single infinite process, but is required to output a bit at each step to a write-only output tape, and otherwise has as many tapes with as large a work alphabet as it wants.

Here’s a Liouville-like example: First design a TM with just one state that pushes a # sign logarithmically slowly across the tape. The one I designed for my thesis uses characters 0,1,2 and a left-endmarker ^ to count in binary up to 2^k after the # has moved for the k-th time. Then create the real-time TM by having it output a 1 each time the # moves, and 0 otherwise. This essentially is Liouville’s number.

• June 4, 2012 3:54 pm

Thanks for clarifying the TM, that concrete example is totally clear.

The wikipedia article has the same problem formula, but there is also no citation for the work. The user who added the blurb to wikipedia, according to the history of their talk page, is the same J. Stubbs. Beyond the error, which could be fixed without much hassle, I don’t think it meets wikipedia’s general notability guidelines and will delete it.

The wikipedia page goes on to say that in base 26, (sort of, the weird underscores don’t make sense) you get all possible strings as a substring of the formula. This is true of both the given formula and Champernowne’s constant, so maybe that’s where the confusion arose.

The wikipedia page also, BTW, cites a citation on a mathworld page, and the citation on the mathworld page is broken. It is sort of a mess. I would say as a personal opinion that none of these formulas is very surprising. I would also venture that none of them are computationally useful. Of course, there are lots of lovely related mathematical ideas, which are notable!

2. Jeffrey Shallit permalink
June 4, 2012 3:50 pm

But you missed the most interesting recent progress on the Hartmanis-Stearns conjecture! Thanks to Adamczewski and Bugeaud, we now know that every number generated by a deterministic finite automaton with output (in the sense made precise below) is either rational or transcendental.

In their model, a finite deterministic automaton accepts as inputs the base-k representation of a number n, and walks around from state to state until the end of the input, whereupon an output is associated with the final state reached, which is a_n, the n’th bit of the number alpha, expressed in base b.

• June 4, 2012 11:49 pm

It’s embraced in the 2012 paper by Freivalds which we referenced at the end about promising results toward proving the conjecture.

3. Jeffrey Shallit permalink
June 4, 2012 7:42 pm

Oh, and the Stubbs formula is simply wrong; it should be

sum(k/a^( (n+1)(floor(log_a(k)) + 1) + (1-a^(floor(log_a (k)) + 1))/(a-1) ), k=1..infinity);

• June 4, 2012 8:10 pm

Thanks! I think some (…)s still need fixing as this has a^ inside a^… OK, I have to break off my marathon homophonic session of “Settlers of Catan” to work it out with pencil and paper :-).

• June 4, 2012 9:00 pm

Ah no, that’s right (but “n” = k, I suspect)—and perhaps Wikipedia’s formatting was missing the internal exponential. The denominator is what I/Stubbs had minus the sum of powers of 10 up to \floor{log_{10} k}, which fixes the extra places noted by DaveAGP. So I’ll go with that fix.

• June 4, 2012 9:10 pm

Or just sum(k/10^a(k), k=1..infinity)
Where a(1) = 1 and a(k) = a(k-1) + floor[log10(10n)]
http://oeis.org/A058183

4. Jeffrey Shallit permalink
June 4, 2012 7:42 pm

I should have said the base is a, so in his formula take a = 10.

5. June 4, 2012 9:49 pm

I suggest that all of these formulas are iterating through numbers one at a time. If you wanted to do better, you could use the fact that the collection of all digits of length i contributes an arithmetic-geometric series, which has an explicit formula. You would get the following, which has no sum symbols, no logs, and no floors.

C = B(1)*10^S(1) + B(2)*10^S(2) + …

where B(i) = AG(10^{i-1}, 10^i – 1, 10^{-i})
and S(i) = i*(10^{i-1}-1) – 9*AG(1, i-1, 10)/10
and AG(x, y, b) = (y*b^{y+1}-x*b^x}/(b-1) – (b^{y+1}-b^{x+1})/(b-1)^2

B is a “base” and S is a “shift” of each group, and AG is the sum of the arithmetic-geometric series sum{a*b^a : a = x..y}.

On a computer, I still don’t think this would change much. I think the arithmetic operations at whatever precision is desired would still dominate, especially if you are doing the underlying math in binary. The naive solution gives the first k decimal digits in O(k) time, which is pretty good!

• June 4, 2012 9:51 pm

Yikes! There is exactly one sum symbol.

June 4, 2012 11:20 pm

This reminds me of a connection Terry Tao observed on his blog between transcendence theory and the Collatz conjecture (which is a statement about the behavior of a particularly simple “counting machine”): http://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/. One conclusion he draws seems to be in the direction you’re going: (a weak form of) the Collatz conjecture implies a very strong transcendence bound.

7. John Sidles permalink
June 5, 2012 6:27 pm

Yet another reason for “seeing where the Hartmanis-Stearns Conjecture goes” (great phrase!) is that it inspires further Hartmanis-style conjectures like this one:

Definition  We say that a real-time Turing machine M is transcendental iff its runtime is not provably real-time (e.g., in PA and/or ZFC) and moreover no provably real-time TM provably computes the same number as M. If a real-time Turing machine is not transcendental, then we say that it is demonstrable.

Conjecture  the existence of transcendental real-time TMs is independent (of PA and/or ZFC).

Here the intuition is that we might make finite progress toward the proving the independence of PvsNP, by considering the (easier?) question of whether transcendental TMs exist.

Here’s hoping the above LaTeX is coded OK! 🙂

• John Sidles permalink
June 5, 2012 8:09 pm

Here the broader analogy is that we have a very natural definition of algebraic versus transcendental numbers, regarding which we can prove many interesting theorems, and propose plenty of interesting conjectures. A parallel 21st century complexity-theoretic challenge amounts to “Does there exist a comparably natural definition of demonstrable versus transcendental TMs, both real-time and otherwise?” AFAICT, this class of question is natural, open, and hard … it appears to be unknown even whether the answers to this class of question are independent of formal systems like PA and ZFC.

• John Sidles permalink
June 6, 2012 5:43 am

On further reflection, it is turning out that class of problem seems to be sufficiently well-structured, with sufficiently many interesting variants, that I will pose it this weekend as a question on TCS StackExchange.

At present the leading candidates for nomenclature are comprehensible versus transcendental languages, and similarly canonically comprehensible versus canonically transcendental TMs that accept these languages.

It may seem strange to conceive that a complexity class as simple as P may contain languages that are transcendental, and it may seem even stranger that the existence (or not) of transcendental languages may be independent of the usual axiom sets. And yet, this is a situation that mathematics has seen before: the Pythagoreans struggled to conceive of irrational numbers, and the Euclideans struggled to conceive that the axiom of parallels could be logically independent of the other Euclidean axioms.

So perhaps 21st century mathematics might beneficially ponder upon the Complexity Zoo’s cryptozoological unknowns … because as Lance Fortnow wrote in his recent review “The Status of the P Versus NP Problem:

None of us truly understands the P versus NP problem; we have only begun to peel the layers around this increasingly complex question.

• June 6, 2012 10:40 am

Dear John, Can you please explain a) your definition, b) your conjecture.

• John Sidles permalink
June 6, 2012 11:41 am

Gil, the question that I asked here on Gödel’s Lost Letter grew out of a question asked last week on TCS StackExchange, namely “Does P contain incomprehensible languages?” Definitions D1D5 of this TCS StackExchange question specify a formal meaning of incomprehensibility.

Now, a week later, reading this wonderful Gödel’s Lost Letter essay “Transcendental Aspects of Turing Machines” has made me wish that I had called these languages (and the TMs that accept them) “transcendental” instead of “incomprehensible.” And so I am thinking about these nomenclatural issues, and hope to pose a concrete follow-up question to TCS StackExchange this coming weekend.

Two broad conjectures associated to this line of thinking are both pretty simple: (1) there’s a naturally transcendental subclass of P that’s more mysterious that we presently appreciate, and (2) there’s a subclass of BQP that’s easier to simulate/approximate with classical resources than we presently appreciate. Considerations relating to verification and validation play a central role in both conjectures.

The strategic goal is pretty simple too: specify math questions and physics objectives for the 21st century that are logically easier than deciding P vs NP, and physically easier than building working quantum computers, yet are comparably fun and touch upon interlocking issues of comparable fundamental and practical consequence.

• John Sidles permalink
June 6, 2012 5:01 pm

LOL … inspired by this Gödel’s Lost Letter essay “Transcendental Aspects of Turing Machines,” notice is hereby given of intent to amend (this coming weekend) “Does P contain incomprehensible languages?” to “Does P contain transcendental languages?” via the substitutions:

incomprehensible $\to$ transcendental
comprehensible $\to$ gnostic

This is done for two reasons: (1) to preserve the parallelism “algebraic numbers are to transcendental numbers as “gnostic TMs are to transcendental TMs”, and (2) to exploit remarkable fact that (apparently) no Mathematical Review has ever used the word “gnostic”.

If anyone objects to this parallelized nomenclature, or can propose a better one, let them speak now!   🙂

• Jim Blair permalink
June 7, 2012 7:17 am

John,

The term “gnostic” seems to have alot of religious connotations that may prove confusing.

• John Sidles permalink
June 7, 2012 8:28 am

There is also Marcus Kracht’s very recent article “Gnosis” (Journal of the Philosophy of Logic, 2011, MR2802332), which concludes with the following (rather foggy IMHO) definition:

When asked whether a formula is true, they [reasoners] either know the answer off-hand or have to decompose it to see what is inside. If its structure conforms with the unpacking mechanism [i.e., gnosis] they can arrive at an answer. If not, difficulties arise that they may not effectively be able to resolve.

Kracht’s concluding passage motivates the Hartmanis-style notion that provable runtime bounds in complexity theory can comprise a logically rigorous and computationally natural proxy for Kracht’s metaphysical notion of gnosis.

Please don’t take the preceding as any kind of endorsement of Kracht’s metaphysics! Indeed, the whole point is to map (foggy) metaphysical gnostic ideals onto Hartmanis-style complexity-theoretic proxies that are computationally natural & logically rigorous. After which task is accomplished, the need for metaphysical understanding of complexity theory is sensibly diminished, and our appreciation of what we can and cannot reasonably expect to know about computational complexity is sensibly increased. Good! 🙂

The focus upon clarity-with-rigor is (for me) the great attraction of Hartmanis’ class of complexity theoretic questions.

• John Sidles permalink
June 10, 2012 9:32 pm

As a followup, the TCS StackExchange question “Does P contain languages whose existence is independent of PA or ZFC?” is now posted.