Alan Turing and His Connections to MATLAB
By Cleve Moler, MathWorks
The popularity of the movie “The Imitation Game” has focused public attention on Alan Turing, one of the 20th century’s most important mathematicians. The film is about Turing’s war-time code breaking and personal life. I am also interested in his unique contributions to science and his influence on MATLAB®.
Turing Machines
In 1936, as a 24-year-old student at King’s College, Cambridge, Turing delivered a paper that was to become the foundation of modern-day computer science: “On Computable Numbers, with an Application to the Entscheidungsproblem.” Loosely stated, the Entscheidungsproblem, or Halting Problem, asks “Is it possible to begin a proof that never finishes?” The question was first posed in 1928 by the great German mathematician David Hilbert. Hilbert challenged mathematicians to formalize the notion of mathematical proof and determine whether it is possible to state a proposition that can be neither proved nor disproved.
Turing formalized the notion of proof by introducing a theoretical machine. This machine had a finite number of states and an infinite tape containing a finite, but unlimited, number of zeros and ones. A set of rules (what we would today call its program) would cause the machine to read a single zero or one from the tape, then possibly erase it and write a new symbol in its place, move the tape one position to the left or right, and transition to a new state. That was all the machine could do. Turing showed that such a machine was capable of proving anything that could be proved by more complicated formalisms.
When he presented his paper, Turing was completely unknown in the field of mathematical logic. His approach was unprecedented. He used his formalism to show that the Hilbert Entscheidungsproblem had no solution—in other words, that it is possible to state mathematical propositions whose attempted proofs never terminate.
The implications of what we now know as “Turing machines” go far beyond this esoteric result. They are the basis of modern computer science, and, in fact, the theoretical basis for the actual computers that we use today.
Turing’s paper was published in 1936, at about the same time as another paper on the Entscheidungsproblem by the American logician Alonzo Church, a professor at Princeton. Turing spent two years working under Church and getting his Ph.D. from Princeton. During this time he also built three of four stages of an electromechanical binary multiplier and began his study of cryptography.
Bletchley Park and Enigma
In 1939, Turing returned to England to join the newly formed, top-secret Government Code and Cypher School at Bletchley Park. This organization’s task was to break the codes used by the German military to communicate with troops in the field, especially those on Uboats at sea. One of these codes employed the German cypher machine Enigma.
Early models of Enigma machines had been in use since the 1920s, so their basic principles were not secret. The details of the model used initially by the German military had been reverse-engineered by Marian Rejewski, a Polish mathematician in the Polish Cipher Bureau, in 1931. The machine has a typewriter-like keyboard, a plug board, three rotors, a reflector, and a display board. When a key is depressed, the electrical signal for that letter passes through the plug board, the three rotors, and the reflector. It then passes back through the rotors in the opposite direction and back through the plug board, where it lights the encrypted character on the display. At least one of the rotors then turns so that a different circuit is used for the next character.
Each day, three rotors were chosen from a set of five. Their initial positions were set according to code transmitted at the beginning of a message. These settings, together with the settings of the plug board and the reflector, determined the message encryption. The number of possible initial configurations was almost 1.6×1017.
Building on work begun by Polish intelligence, Turing designed an electromechanical machine known as the Bombe. This machine would eliminate configurations that generated decrypted messages failing to contain a specified crib, or given plaintext. For example, digits were often spelled out, and so the word “eins”, for “one”, was a frequent crib.
Turing’s group was so successful at decrypting German messages that Britain’s military had to disguise their responses to hide the fact that they came from intercepted communications.
The Bombe was not yet a full-fledged computer—it had no memory, it was “programmed” by setting switches and inserting patch cords, and its logic units were relays.
An Automatic Computing Engine
Immediately after the war, universities and research laboratories in many countries began to build stored-program electronic computers. In February 1946, while he was working at the National Physical Laboratory (NPL) in Teddington, Turing presented his own design for a stored program machine that he called the ACE (Automatic Computing Engine).
The design for ACE was based on concepts from Turing’s theoretical work on computability and on his code-breaking experience at Bletchley Park, where he had been involved with the development of a machine called Colossus. Colossus was built to help with the cryptanalysis of the German Lorenz cipher. It is often regarded as the world’s first digital computer, although, since it did not have a memory, it was not a stored-program computer; it was programmed by paper tape, plugs, and switches. Turing hoped the ACE could be built by the engineering team that built Colossus, but the Official Secrets Act prevented him from explaining that his design for ACE could actually be implemented.
Turing’s design for the ACE was far more ambitious than machine designs being proposed elsewhere. It included an early form of a programming language called Abbreviated Computer Instructions, and Turing believed that much of the work could be done in subroutines, with different sets of subroutines used for different tasks. His ACE was indeed inspired by a Universal Turing Machine.
Unaware of the computing successes at Bletchley Park, the NPL management was reluctant to approve Turing’s elaborate project.
Turing became frustrated at the bureaucratic delays, and eventually left NPL. In 1948, he accepted a position at the University of Manchester, where computer development was proceeding more quickly.
A Growing Interest in Matrix Computation
In 1947, while he was still at NPL, Turing wrote a paper titled “Rounding-off Errors in Matrix Processing.” This was before anyone had actual experience with automatic digital computers. Up to that point all computing had been done by hand. Although the terminology used in the paper is not quite what we would use today, the 13 section headings could serve as the syllabus for a modern course on matrix computation.
For example, Section 3 is “Triangular Resolution of a Matrix.” The principal result is
THEOREM ON TRIANGULAR RESOLUTION.
If the principal minors of the matrix A are non-singular, then there is a unique unit lower triangular matrix L, a unique diagonal matrix D, with non-zero diagonal elements, and a unique unit triangular matrix U such that A = LDU.
When we absorb D into U, this becomes the LU function in MATLAB. The result was not original with Turing. It also appears in another 1947 paper by von Neumann and Goldstine, which Turing references, and had appeared in other papers before then.
Section 4 is “The Elimination Method.” Gaussian elimination is described in words and related to LDU “resolution.” The fact that solving a set of n equations involves \( \frac{1}{3}n^3 + O\left(n^2\right) \) multiplications is discussed. But there is no mention of the need for pivoting.
In Section 8, “Ill-Conditioned Matrices and Equations,” Turing uses the term “condition number” for the first time in the literature, and presents some of its properties. However, the definition is not expressed in terms of what we now call a compatible matrix norm.
John Todd developed the notions of matrix norms and condition numbers in a series of papers in the 1950s. Several other authors wrote about condition numbers, as well. By 1959, when I studied numerical analysis with Todd at Caltech, the concept was on a sound footing. I don’t remember if he mentioned Turing. Now we have norm, cond, and condest in MATLAB.
The last four sections of Turing’s paper deal with round-off errors. Turing’s entire analysis is based on a quantity denoted by ε, the error made in one step of elimination. This error can be observed and controlled in hand computation but not in automated computation on a modern machine with a fixed word length. Because Turing was not concerned with pivoting and scaling, his analysis does not consider the possibility that ε might grow during the elimination.
The Pilot ACE
With Turing’s departure from NPL, his assistant, J. H. Wilkinson, took over leadership of the group. A simplified version of the ACE, known as the Pilot ACE, was built instead of the full machine. The first program on the Pilot ACE was run in May 1950, and the machine was officially demonstrated in December of that year. Wilkinson designed and built the arithmetic unit. Since Turing’s design meant that multiplication was done in a subroutine, Wilkinson was able to introduce floating-point arithmetic as soon as he realized it was desirable.
The Pilot ACE used mercury delay lines for its main memory. At first, there were only 128 32-bit words of memory. That was later expanded to 354 words. A 4096-word drum was added in 1954.
The machine was originally intended to be experimental, but it was so useful that it was kept in operation for several years. One application, publicized by the BBC, involved modeling metal fatigue in a Comet jet airliner. A commercial version of the Pilot ACE known as the DEUCE was produced by British Electric. Altogether, 33 Pilot ACE machines were made between 1955 and 1964.
Wilkinson and the Beginnings of MATLAB
Jim Wilkinson continued to head the Pilot ACE project, as well as work on numerical analysis. He went on to become the world’s leading authority on matrix computation. His research on matrix eigenvalue algorithms was published as a series of papers, with various coauthors, in Numerische Mathematik. The work was eventually collected in Handbook for Automatic Computation, Volume II, Linear Algebra, 1971, with coauthor Christian Reinsch.
Wilkinson’s Algol procedures in the Handbook were translated to Fortran by a group at Argonne National Laboratory. This version became EISPACK (Eigensystem Package). I was part of the EISPACK project. I wrote the first version of MATLAB so that my students could get access to the package without writing Fortran.
I never met Alan Turing. I was 15 years old when he died. I wonder what he would have thought of MATLAB.
Introducing the MATLAB Enigma Emulator
By Corey Lagunowich and Seth Popinchalk, MathWorks
Although the Enigma machine was a purely electromechanical device, the desire to break its code sparked some of the earliest innovations in software engineering. What would Enigma look like in software instead of hardware?
To find out, we developed a MATLAB app that simulates the Enigma machine (Figure 1). By happy coincidence, nine Enigma machines—one of the world’s largest collections—were on display at the Museum of World War II in Natick, Mass., just two miles from the MathWorks headquarters. The museum gave us access to one of them while we were developing the app.
Figure 1. The Enigma M3 Emulator MATLAB app.
Figure 2 shows key components of the M3 Enigma machine. Pressing a key causes current to flow through a plug board, three rotors, and a reflector, lighting one of the letter lamps above the keys. Each individual plug, rotor, and reflector performs only a simple substitution cipher, but when they are used together there are over 150 quintillion possible combinations—and with at least one rotor turning one position with each key press, creating another combination, decrypting their messages was a colossal challenge.
Figure 2. Inside the Enigma machine. The reflector and rotors permute letters of the alphabet to encode or decode the message.
All the Enigma encrypting components are modeled in MATLAB as permutation matrices. For example, the rotor on the right, which always rotates with each key press, is modeled by
I = eye(26); Right = 'BDFHJLCPRTXVZNYEIWGAKMUSQO'; [~,p] = sort(Right); R = I(p,:);
Additional permutation matrices, L, C, F, and P, for the left and center rotors, the reflector, and the plug board, are created with similar code, initialized with other strings.
To model the effect of a rotor advancing, the permutation matrix is modified using the MATLAB circshift function.
R = circshift(R,[-1,-1]);
A series of if-then statements determines which rotors advance during each key press.
A single character cin typed at the keyboard is converted into a logical column vector xin with
xin = logical(zeros(26,1)); k = cin-'A'+1; xin(k) = 1;
Now the entire encryption process, transforming an input xin to an output xout, is neatly reproduced with code using matrix left division to model the path of the current through the rotors in the outbound direction, and matrix multiplication to model the inbound path.
M = L*C*R*P; xout = M\F*M*xin;
The reflector matrix F is actually a symmetric permutation matrix, and so the matrix ultimately defining the transformation, M\F*M, is also symmetric. This is why the process of decoding an Enigma message uses the same initial settings as encoding one.
To complete the process, the output character is retrieved with
k = find(xout)+'A'-1; cout = char(k);
The MATLAB Enigma M3 Emulator is available for download from the File Exchange on MATLAB Central.
For Further Reading and Viewing
Andrew Hodges, Alan Turing: The Enigma, Vintage, Random House, London, and Princeton University Press, www.turing.org.uk/book.
Cleve Moler, “Jim Wilkinson,” Cleve’s Corner Blog, mathworks.com/cleve-wilkinson.
“The Pilot Ace,” youtube.com/watch?v=Sf28IJmm-P4. This rare video features Wilkinson and Mike Woodger, in 1982, reminiscing about the Pilot ACE computer. I recommend it to anyone interested in the history of computing.
1©2015 The MathWorks, Inc. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled “GNU Free Documentation License.”
Published 2015 - 92913v00
