Transcendental Aspects of Turing Machines
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 appears with frequency approaching among the first digits as grows. Not even and 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:
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:
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:
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 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 . If is an irrational algebraic number, then the inequality
can have only a finite number of solutions where are relatively prime integers.
To illustrate the difficulty, no way of computing a bound on is known given and .
A Turing machine operates in real time if it reads an input and writes an output at each step. For computing digits of a real number the input is , 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 th step, for some fixed , 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 that can be extremely well approximated by rational numbers: for all and there exist integers such that
Liouville proved that every such number is either rational or transcendental. Any number such that the th nonzero digit comes in place where 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.
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 that runs consecutively through the values 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 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 and —top and bottom. Imagine that they are stored on separate Turing tapes and that the heads are arranged as depicted below:
In this case is the lead counter, and its value is more than the counter . The machine proceeds in the following manner: the head on moves left to right and outputs the value of the counter. The head on the counter moves right to left and adds to the counter’s value. That is right, it adds . In this way the next state of the machine is:
The critical point is that now is the lead counter. This allows the machine to repeat the same operation with the roles of and exchanged. Clearly, this all works, and the machine can continue doing this forever.
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:
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.
Another cool case would be we can use HSC to resolve an open problem. Suppose that we could use it to prove that is transcendental, which is still open. This would be great. We covered new algorithms for the digits of here and here, though this still falls short of what’s needed to invoke the conjecture.
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 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.
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]