Happy Unbirthday To Turing
Happy 100th birthday to our great Machine Tools provider
Alan Turing was born 100 years ago yesterday. Hence today is his first unbirthday since his one hundred birthday. Per Wikipedia, an unbirthday is an event that can be celebrated on any day that is not the person’s birthday. It was created by Lewis Carroll in his celebrated novel Through the Looking-Glass.
Today we speculate on what Turing would find most amusing about what he helped create.
Of course many of his near-contemporaries are giving their own impressions at celebratory conferences around the globe, including ACM San Francisco a week ago, Cambridge University this past week, and Manchester right now.
We decided at GLL that we could not compete with all the celebratory events, dedicated pieces, and speeches that are being given for him. These will no doubt, like the earlier Princeton Turing Celebration, talk about how great his work was, how ground-breaking it was, and how he helped create computer science itself as a new discipline.
No we cannot compete with all these, but we do feel we could put our own spin on what developments would most bemuse Turing. Recall that “bemuse” means:
to cause to have feelings of wry or tolerant amusement.
Turing Is Not Amused
Since Turing was a British subject, we are paraphrasing the famous statement “We are not amused.” See here for this quote:
This supposed quotation was attributed to Queen Victoria by Caroline Holland in Notebooks of a Spinster Lady, 1919. Holland attests that Victoria made the remark in 1900, but supplies no details of the circumstances. Other reports have suggested that the line wasn’t an example of the ‘royal we’, but that Victoria was speaking on behalf of all the ladies present at court.
We contend that the following “obvious” examples would not be the things that would most amuse Turing:
- He would not be most amused by the sheer technology advances. Yes an iPhone, an iPad, a laptop, and all the other gadgets are remarkable. But he was already thinking beyond Siri.
- He would not be most amused by chess playing programs being better than world champions.
- He would also not be most amused by the other advances in what we now call AI.
You may or may not agree. But surprise is not the same as being amused—or bemused.
Turing Is Amused
So what would he find most amusing? We believe—perhaps you will too—that it is the long staying power of his machine model that we now call Turing machines. And the unfortunate inability for us, over 70 years later, to have any idea of their limitations.
His proof that they cannot solve the Halting Problem was brilliantly mutated into proofs that Turing machines with computational limits on time and space and other measures also are restricted in their abilities—with respect to the same measure. But today, beyond the kind of diagonalization results due to Juris Hartmanis and Richard Stearns and a few others, there is precious little that we can prove about his famous machines. Ken and I find this dual success and failure—his machines are still the model of computation for theory and the diagonal proof is still the only way we can prove restrictions on their power—what might amuse Turing the most.
In the next sections we would like to expand a bit more on this point, and also show how versatile Turing’s machines are. His formalism not only founded a science—computational complexity—that didn’t really begin until a decade after his death, it still has growing room.
The Multi-Tape Turing Machine
Turing showed how the universe can be encoded onto a single one-dimensional tape. This is what Google’s Turing 100 doodle shows.
The only extension complexity theorists ask for is to have any finite number of tapes. The first tape conventionally receives the input , and optionally the last tape provides the output . Both and are strings over an I/O alphabet , while the machine employs a larger work alphabet , which includes the blank character . The machine has a finite set of states , which includes the start state and a set of designated final states. Let stand for directions to move one cell left or right or to stay, respectively. Then all we need to specify a Turing machine is to give a subset
of instructions , where are states with allowed, and the other components are -tuples of chars or directions.
Mathematically that’s all is—we need to mention tapes and heads only to execute . To define a computation we need that every configuration includes the current state and the characters currently scanned on the tapes. Find an instruction that begins with and , change the characters to , move heads per , and go to state , setting up the configuration for the next move. Start with and and everything else blank, and halt if and when you reach a configuration with no applicable instruction. The language is the set of that have a computation that halts in a state in .
The time is the number of steps it took to halt. is deterministic if is a partial function on , so there is always at most one applicable instruction and hence one computation. is the class of languages of machines whose accepting computations all have length , and the subclass when is deterministic. Complexity theory in a nutshell.
TM Definitions for Everything
The real power of this formalism is how easily other important concepts can be defined from it. Conditions apply to every instruction.
- Finite Automaton: ; and .
- Pushdown Automaton: ; , , .
- Linear Bounded Automaton: ; .
The notions of language accepted and (non-)determinism factor right in—for instance, a finite automaton halts on the following and accepts iff the current state is in . Thus Turing gives us Noam Chomsky’s hierarchy.
- Space complexity of a computation: the number of cells whose character was ever changed and re-read.
- Reversal: when a head moves having previously moved , or vice-versa.
- Reversal complexity: the total number of reversals.
- : The class of languages accepted by polynomial-time deterministic TM’s that make reversals.
Thus we can define the class of problems with fast parallel algorithms without having to define a parallel machine. Can we define streaming algorithms? Well, we can try:
- Streaming machine: All tapes either use space or are limited to reversals.
Let be the class of languages accepted by streaming machines that also run in polynomial time. Then contains both and , the latter named “Steve’s Class” after Steve Cook. Is it in some sense a closure of both classes? What if poylog is replaced by log?
Here are some concepts that lend themselves to more-stringent notions of streaming and have other uses.
- Online machine: , wlog. .
- Real-time input: .
- Real-time output: , .
- Sequence generator 1: Input is empty, , .
- Sequence generator 2: Input is , , , , .
- Fixed stride on tape : for some fixed the head moves right every th step and is stationary otherwise. Similar concept with “left” in place of right, and allowing worktapes to alternate phases of each.
Thus we can talk about streaming in real time or some fixed stride, not just for the input and output tapes but also for the non-logspace or non-polylog-space worktapes. Turing’s flexible framework allows many handles on the processing of information. This even goes for oracle machines—Turing defined those too.
Is TM Linear Time “Right”?
Turing machines are equivalent to many models for defining polynomial time, but as surveyed here, linear or other fixed polynomial time bounds are not so robust. Most of those models, including random-access machines and TM’s with planes instead of tapes, can do computations that TM’s provably cannot imitate step-for-step, even with some fixed delay. This does not prove they accept more languages in linear time, but that is plausible. Nevertheless we may ask:
Are these richer models technologically scalable? Or is the more-restrictive Turing-tape notion of linear time “correct”?
The richer models do not charge for poor locality of reference, something you can actually feel whenever a program making many small random-access reads causes page faults and “thrashing” of disks. Whereas, Turing tapes have affinity for streaming and pipelining and embody the technological notion that “locality is one-dimensional.” But what can distinguish the Turing machine notion of linear time?
One is that the standard circuit-complexity notion of -uniformity really defines the circuits’ connection languages to belong to TM linear time, because the inputs to these languages have encodings of size . What makes this uniformity notion salient is the way Turing machine computations lend themselves to definability in first-order logic. The language classes of non-deterministic and alternating linear-time TMs have notable equivalent characterizations.
The “purest” indicator, however, may be the truth of the Hartmanis-Stearns Conjecture, which we have been discussing. This connects Turing machine linear time to the classic concepts of rational, algebraic, and transcendental number. Although it is for sequence generation, not language acceptance, the linear structure of Turing’s tapes is the key feature.
Is an interesting class? Does it have a simple characterization via known classes? Could it equal ?
If the Hartmanis-Stearns conjecture is false, can one give a natural, more-restrictive notion of linear time that makes is true?
Can the function on inductively defined by , , , be computed by linear-size circuits? It moves all 2’s flush-right while leaving the sequence of 0’s and 1’s the same, e.g. . See this guest post by Ken on the Computational Complexity blog.
[changed/added sentences with “unbirthday” and “oracle” and “salient”]