Monday, April 27, 2015

Alan Turing - Accidental Inventor of the Stored-Program Computer

Intro

Humans have been inventing better, faster, and more accurate ways of doing computation for literally thousands of years. Examples of this idea include Archimedes' Antikythera Mechanism, considered the first analog computer (Wallis, 2008) from about 100 B.C. to Charles Babbage's Difference Engine in 1822 ("Difference engine - Wikipedia, the free encyclopedia," 2015), to the "First Computer Program" Lady Ada Lovelace devised to run on the Difference Engine ("Ada Lovelace - Wikipedia, the free encyclopedia," 2015), and Hollerith's punched cards for the 1890 census ("Punched card - Wikipedia, the free encyclopedia," 2015).
Among the prestigious company mentioned above, a name that cannot go unmentioned is Alan Turing. Recently, Dr. Turing has received a royal pardon and other much-deserved publicity and he is well known in Computer Science circles for invention of his "Turing Test" for Artificial Intelligence. While Turing is widely recognized for his contributions to cryptography in World War II, what is sometimes overlooked is his accidental contribution to general computer science and the impact it made on the war effort at the time.

From Theoretical Mathematics to Computers

Originally, Dr. Turing was writing a paper on mathematics called "On Computable Numbers, with an Application to the Entscheidungsproblem" (Turing, 1937, p. 230). In summary, Dr. Turing was attempting to answer the question, does there exist an algorithm that can prove every mathematical statement, no matter what it is, true or false? This, then, is the essence of the Entscheidungsproblem, or Decision Problem (Weisstein, n.d.).

To help answer this question, Dr. Turing described a computing machine capable of reading and writing "symbols" to a paper tape. This machine could be programmed with a set of internal rules before starting to read the tape and the combination of the previously read symbol and the configuration would constitute a new configuration - essentially equivalent to the machine state.
Eventually, this like of thought lead Dr. Turing to ask if the computer is capable of all possible computations, then is it possible for one computer to read another computer's code and determine if it will halt or go on forever. Turing was able to prove that it was not possible to create a program to read another program and determine if it would halt and then used this fact to prove the original question - that there is no way to always say if a mathematical statement is provable (Campbell, n.d.).

From Paper to Big Iron

Perhaps more important than the proof in Dr. Turing's paper was the almost off-handed mention of storing "symbols" on paper tape which can be read by the computer and will affect its state. It doesn't take much imagination to realize that this is the conceptual model for a stored-program computer.
While it is probable that the stored-program computer would have come about as a natural evolution of humanity's  quest for mechanical calculating machines however we will never know. Shortly after Turing's paper was published the world was plunged into a war that found several countries clamoring for better and faster calculations.
Mathematician John Von Neumann is generally credited with invention of an early computer architecture that, among other things used the stored-program concept ("Von Neumann Architecture") for his work on the EDVAC computer and the associated paper published in 1945 "First Draft of a Report on the EDVAC." Von Neumann was working on The Manhattan Project at the Los Alamos National Laboratory - a computationally bound project. It is unknown whether Von Neumann was aware of Turing's paper but it is worth noting that Von Neumann was at Cambridge in 1935 and Princeton from 1936-1937 at the same time as Turing and the two were, in fact, acquainted ("Von Neumann architecture - Wikipedia, the free encyclopedia," 2015).
Prior to the EDVAC, the ENIAC computer was the state of the art in computation however it had a few drawbacks. Namely, it had no stored-program memory. Programming was quite literally done by the error-prone process of rewiring the circuitry and could take three weeks to program ("Von Neumann architecture - Wikipedia, the free encyclopedia," 2015).
At about the same time, Turing was working for England's Bletchley Park, site of the Government Code & Cipher School. He created the Bombe electromechanical machine that helped find German Enigma machine settings but was not a calculation device. It was more of a brute-force decryption device, having several Enigma machines wired together ("Bombe - Wikipedia, the free encyclopedia," 2015).
More importantly to the topic at hand, Turing also contributed to the Colossus project - a top-secret stored-program computer used by Bletchley Park for decryption of the Lorenz cipher (Copeland, 2006). Although the Colossus was designed by an engineer named Tommy Flowers with Turing's work on probability being incorporated in the design. Ironically, due to this work, Turing knew that the stored-program concept was feasible before the Von Neumann paper but was not allowed to reveal this fact due to the secretive nature of the Colossus project. 

References:


Ada Lovelace - Wikipedia, the free encyclopedia. (2015, April 22). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Ada_Lovelace#First_computer_program
Bletchley Park - Wikipedia, the free encyclopedia. (2015, April 12). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Bletchley_Park
Bombe - Wikipedia, the free encyclopedia. (2015, April 13). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Bombe
Campbell, M. (n.d.). New Scientist TV: See how Turing accidentally invented the computer [Web log post]. Retrieved from http://www.newscientist.com/blogs/nstv/2012/06/how-turing-accidentally-invented-the-computer.html
Colossus computer - Wikipedia, the free encyclopedia. (2015, April 27). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Colossus_computer
Copeland, B. J. (2006). Colossus: The secrets of Bletchley Park's codebreaking computers. Oxford: Oxford University Press.
Difference engine - Wikipedia, the free encyclopedia. (2015, February 15). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Difference_engine
Punched card - Wikipedia, the free encyclopedia. (2015, April 9). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Punched_card
Turing, A. M. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of The London Mathematical Society. doi:10.1112/plms/s2-42.1.230
Von Neumann architecture - Wikipedia, the free encyclopedia. (2015, April 12). Retrieved April 27, 2015, from http://en.wikipedia.org/wiki/Von_Neumann_architecture
Wallis, P. (2008, July 31). Ancient Greek computer from 100 B.C.: Archimedes strikes again? Retrieved from http://www.digitaljournal.com/article/258045
Weisstein, E. W. (n.d.). Decision Problem -- from Wolfram MathWorld. Retrieved from http://mathworld.wolfram.com/DecisionProblem.html


No comments:

Post a Comment