Why Alan Turing Has Already Won, No Matter How The Imitation Game Does at the Oscars
February 20, 2015 — Hector Zenil, Editor of the Complex Systems journal
When I was invited to join the Turing Centenary Advisory Committee in 2008 by Professor Barry Cooper to prepare for the Alan Turing Year in 2012, I would have never imagined that just a few years later, Turing’s life and work would have gained sufficient public attention to become the subject of a Hollywood-style feature film, nor that said movie would go on to earn eight Oscar nominations.
The Imitation Game is in essence a rather accurate summation of the life and brilliant work of Alan Turing, even while some aspects of the movie are clearly fictional. Turing was in many ways a victim of his great achievements—he was forbidden from telling of his accomplishments during the war to anyone, including his family. Imagine you have the chance to save the world—and you do so—but you are required to keep it confidential; that was the case of Turing and his colleagues at Bletchley Park. He was also prosecuted toward the end of his life in an unfair turn of events. Nevertheless, Turing was never engulfed by his circumstances and remained interested in what can be considered the greatest questions in science and beyond, from what intelligence is in both humans and machines to what mechanisms nature harnesses to produce forms and shapes, and ultimately life itself.
At Bletchley Park, Turing, together with other mathematicians and engineers of great talent, made longstanding contributions to science and to human history by building the first automated machines to decipher encrypted messages. His work and the work at Bletchley led to what is today one of the greatest intelligence agencies—the UK Government Communications Headquarters (GCHQ). One can play with a computer program online to see the inner workings of the famous Enigma machine used by the Germans to encode their messages, which Turing and his team were able to crack. The example below from the Wolfram Demonstrations Project shows the inner workings of such an encryption machine that used cylinders to scramble and conceal the contents of messages during World War II.
It is worth taking a minute to see how computers, and ultimately the human race, have come this far, with Turing himself playing a central role. Turing approached several scientific endeavors with incredible idiosyncrasy. When tackling what would become his most seminal work, which gave rise to the digital computer, Turing was actually not thinking of computers but of humans. Indeed, he asked how humans calculate and how much of that could be captured by mechanical calculation. By pursuing this idea to its final consequences, Turing revealed two incredibly powerful concepts of priceless intellectual value.
Turing first showed that either a human or computer with the same resources would find a fundamental limit on the sort of things that could be proven to be true or false about a theory. In other words, there are formally unanswerable questions whose answers are nevertheless known to be true or false; hence, truth and proof are separate concepts. Indeed, in this very technical formal approach, not all truths can be proven by mechanical means.
At the same time, Turing also found that he could build a single machine to do the work of any other computing machine; this is what we call a “computer” today. Computers that are capable of emulating any other computer are called “universal,” because they can do whatever any other machine can do. You can check email, watch videos, and play video games all on the same computer, as it can be reprogrammed to perform multiple tasks. That’s obvious to us now, but it wasn’t at all obvious to someone living in the 1930s.
An “a” machine, as Turing would first call it (for “automatic”), today known as a Turing machine, is the most basic unit of study in the field of theoretical computer science. The concept not only gave birth to the whole field but remains the object of reference for most purposes in computer science. For example, when you want to know how much memory one theoretically needs to perform a computation, a universal Turing machine is always the point of reference. An immediate follow-up question is whether this kind of “universal” computation occurs naturally in the world and is responsible for the complexity and structure we find in the universe.
One way to answer this question is to look at how many resources are required to build such universal computers. If it turns out that this type of computation is very easy to implement because it requires only a few simple resources, one might be persuaded that nature makes use of this computational resource to produce the shapes and patterns we find around us. And indeed, it turns out that the resources needed to implement a universal computing machine are so incredibly simple that they are available everywhere in nature. This was illustrated by a competition sponsored by Stephen Wolfram to prove whether an exceptionally simple Turing machine that he had found in his exploration of these computers in his book, A New Kind of Science, was actually capable of universal computation. The contest started and ended in a heated but rich discussion on the necessary and sufficient initial conditions for a system to become and be considered universal.
The machine above starts with an empty “tape” on which a reading “head” is placed; the head moves to the right or left and writes or deletes colors over time following the rules displayed at the bottom. While this small Turing machine requires a special initial condition to perform as a universal computer, it does not violate any previous result in the field, and thus meets the conditions for a system to be universal. An excellent place to learn about this rich computing model can be found here, and more about the smallest universal Turing machine here.
Another question related to Turing’s main interests is about the shapes and forms that emerge in nature all around us, especially in connection to life. By looking at another, but equivalent, type of computing program that Stephen Wolfram introduced in the 1980s called 1-dimensional cellular automata, one can quickly see that computer programs are incredibly rich in behavior, and that even the simplest computer programs can display an incredibly complex range of behavior. Below (see pyramidic figure) is a minimalistic computer program of this type with only three colors—an example of Wolfram’s 1-dimensional cellular automata—that starts from the simplest possible initial condition (a single dark cell at the top) and replaces the cell according to a simple set of rules (see top figure) that looks only at the neighbor’s colors to determine the color of the next central cell.
The program produces all sorts of simple and complex patterns that interact without destroying each other. There is even a small transient at the intersection of the rightmost fractal behavior and the middle one where regions of high complexity emerge just before dying out, whereas on the leftmost side there is a stripe of regular behavior feeding a seemingly never-ending, random-looking region that expands over time. The digital computers that humans produce may be simply imitating the computations that occur naturally throughout the universe, and that are, indeed, the very basis of how the universe functions.
Among the many interests of Alan Turing was the challenge of mathematical notation, which he explored in a manuscript, “Notes on the Foundations of Computer Science,” to be auctioned on April 13 of this year. Wolfram Research has built on Turing’s ideas since its beginning, and the topic of mathematical notation has also been key to the development of Wolfram Mathematica and the Wolfram Language. It is the Wolfram Language that enables Wolfram|Alpha, the world’s only computational knowledge engine, to understand queries in both formal and natural language. Stephen Wolfram has written and spoken extensively on these matters.
Recently Wolfram Research has taken an interesting direction toward pervasive computation (and related to Turing’s seminal idea of universal computation) with Wolfram Programming Cloud, bringing revolutionary technology to the real world for creating and deploying software and applications to anywhere, from anywhere. Also, the Wolfram Connected Devices Project takes us closer to the goal of injecting the power of universal computation even in the simplest devices from the Internet of Things, effectively making any physical device into a universal Turing machine. Devices like the Raspberry Pi mini-computer, already powerful in its own right, is made even more so by being shipped with the Wolfram Language and Mathematica preinstalled, enabling inquiry and exploration for the next generation of scientists and makers.
Much still remains to be discovered in connection to Turing’s main ideas, as it may turn out that the universe itself is some sort of universal Turing machine. In fact, as far-fetched as this might sound, it is exactly what classical physics prescribes: a fully deterministic world governed by computable rules and therefore emulative by a simple computer program such as a Turing machine. When physicists explain their ultimate quest for a theory of everything, they are endorsing just such an idea. Stephen Wolfram has his own approach to tackle this challenge and anticipates this being one of his next major projects as time permits.
Wolfram|Alpha shows a spike in the number of visits to the Wikipedia entry for Alan Turing on several important dates in modern history. First, the official public apology given by British Prime Minister Gordon Brown on September 10, 2009, and then around several academic events in late 2011 and early 2012. We see a great spike exactly on the 100th anniversary of his birthday on June 23, 2012—and by strange coincidence, as Stephen Wolfram notes in recognizing Turing’s 100th birthday, Mathematica’s anniversary also falls on June 23 (1988). Another spike occurs on December 24, 2013, when a posthumous royal pardon was granted for Turing’s 1952 conviction for homosexuality. More recently, there has been a steady increase due to the release of the movie The Imitation Game.
Regardless of the outcome of the Oscars awards this Sunday, in a way, Alan Turing has already won. The achievements of Turing, widely considered to be the father of modern computing, are now known worldwide, in ironic contrast to the unfortunate circumstances that led to his death. While he accomplished much in his relatively short lifetime, the best way to remember Turing is by continuing to advance his greatest ideas with the same kind of eagerness that he always had toward scientific inquiry, and by finding answers in unexpected directions. At Wolfram Research, we strive to do exactly that.