Alan Turing: Tech Ideas that revolutionized 20th Century
Turing over his lifetime produced various groundbreaking seminal papers and works. In this write-up, I am going to delve into four such major works: “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936); Bombe and Spider, Banburismus (1940–41); Computing Machinery and Intelligence (1950); Solvable and Unsolvable Problems (1954).
On Computable Numbers, with an Application to the Entscheidungsproblem (1936)
David Hilbert and Wilhelm Ackermann discussed Entscheidungsproblem in their 1928 writing, The Principles of Mathematical Logic. They posed universal validity and satisfiability, which customarily was referred to as the decision problem (Hilbert et al., 1950). The decision problem can hence loosely be defined as coming up with an algorithm that takes an input and replies with a Yes or No depending on whether the statement is universally satisfiable.
Turing came up with an Automatic-machine that has the capability of punching symbols of any defined alphabet (0,1 in the case here) on an infinite long magnetic tape. The machine could read, write or erase symbols from the magnetic tape; it can shift across the magnetic tape in either of right/left directions at once. Besides, an m-configuration is also maintained which has the capability of keeping track of r conditions. Later, based on the read symbol, and the m-configuration, the machine either goes to the next instruction or halts. (Turing & Copeland, 2004)
With the help of his machine, Turing proved that the Entscheidungsproblem problem cannot have any solution ie it is unsolvable.
Bombe and Spider, Banburismus (1940–41)
The Enigma machines made by Germans to help them send cryptic messages were produced using a polyalphabetic substitution cipher. Much of the effort that went into breaking it is accredited to Turing. The Bombe was designed by Turing along with Gordon Welchman, to help break Enigma messages. The Bombe identified possible initial positions (configurations) of the steckers and rotor motors(The History of Hut Eight, n.d.), ie the details needed to uniquely replicate the configuration of Enigma and possible substitution cipher.
As possible configurations run into trillions, Turing came up with Banburismus whose aim was to reduce the number of possibilities to be tried on Bombe. The idea of Banburismus was based on conditional probabilities.
Computing Machinery and Intelligence (1950)
In this work, Turing discusses the ‘imitation game’ (later known as the Turing test). The Turing test consists of three participants: A computer, a human interrogator, and another human. The task of the interpreter is to ask questions to the other two entities and try distinguishing which one of them is a computer and which is a human. In the test, all communication takes place with the help of the keyboard and screen. The other human, according to Turing’s writing, must aid the interpreter in making correct identification. If a computer plays the test successfully, it may be seen as the computer having an ability to think.
Turing in his writing, allows the interpreter to ask any range of questions, which may help them identify the machine from the human.
Solvable and Unsolvable Problems (1954)
Turing talks about what it could mean for a problem to be unsolvable. He gives examples of the movable square puzzle. Where given a 4x4 square palette with 15 squares arranged in one order, the player is asked to move one square at a time with the help of the empty square, in such a way that a 1–15 configuration can be obtained. He suggested that given a state it is possible to say if 1–15 config can ever be reached or not (ie depending on the state and number of interchanging it needs to settle a particular square tile to its right position, this may be answered).
Bibliography
Hilbert, D., Ackermann, W., & Luce, R. E. (1950). Principles of mathematical logic. AMS Chelsea.
The History of Hut Eight. (n.d.). Retrieved October 27, 2021, from http://www.ellsbury.com/hut8/hut8-000.htm
Turing, A., & Copeland, B. J. (2004). The essential Turing: Seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma. Clarendon Press ; Oxford University Press.
