We picked up right from where we left off the previous Wednesday, and as part of a brief review we discussed the moral and political consequences of code breaking.

The primary example of this dilemma involved the British losing fifty to eighty of their ships a month. As this was basically as fast as they could build them it was an obvious problem, with the loss of life compounding the issue. There was an Enigma encoded message that the British intercepted from the Germans that, upon decoding, revealed the location of nine German warships. The Royal Navy didn’t want to let on that they had broken Enigma, lest the Germans change the cipher again, so the British destroyers were only told the location of seven of the ships, with command fearing that if all the ships were sunk the Germans would catch on. The destroyers, however, ran into the other two ships on their way to sink the seven, and sunk them as well. Despite this, the Germans were so sure that Enigma was unbreakable that they assumed there was a spy somewhere in their ranks. They didn’t consider the possibility that Enigma could be at fault.

Moving on, we discussed another decrypting machine that was employed in the British war effort: Colossus. Colossus was a giant computer that was designed not to crack Enigma, but to crack the Lorenz cipher, a code that was used between Hitler and his field generals. In some ways it was more advanced than the Enigma decryption techniques that Turing and the British cryptographers employed – it used 1500 vacuum tubes and was the first machine to employ them for computation – but it also looked for matching keys using brute force. Once a matching key was found, the user had to manually do the decryption.

Turning to the reading, we first reviewed Turing’s paper “On Computable Numbers.” It was quickly apparent that few people in the class understood much of Turing’s paper beyond a basic outline and what he was trying to prove, so we started breaking it down.

We first covered some background, why the paper was written in the first place. The mathematician David Hilbert wanted mathematics to be complete and encompass all knowledge, and to be a system where every presented problem could be solved. Kurt Gödel came and showed that, actually, this wasn’t possible in his paper “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” This was a difficult to understand paper, but Turing’s paper made it more comprehensible by using something he called a Turing Machine to help explain his ideas.

We then took some time to define a Turing Machine, and Dr. Wagstaff took the time to draw one on the board. A Turing Machine is made of some sort of input/output system, in this case a tape, and something that can read and write to the tape. The tape contains various symbols, all of which are contained in a possible set of symbols. In the drawing to the right, the current symbol is denoted S_i. The machine also has a configuration q_i, which we’d refer to as a ‘state.’ In this state is implicit memory, for example, if you’re in state one and see an A, do this, if you’re in state 2 and see an A, do that. This description helps to clarify the tables in the book. These tables are examples of Turing programs, and the example Dr. Wagstaff drew below. What the machine would do in reading these programs is read the state q_i, read the symbol S_i, print a symbol S_k based on certain parameters (or not), and then move to the state q’. Additionally, an entire Turing Machine can be recorded as a number. This is crucial because another Turing Machine can then read in that number and simulate that machine.

So how is this relevant to the mathematical completeness that Hilbert so wanted and Gödel and Turing showed wasn’t possible? It comes down to the Entsheidungs Problem, also called the Decision Problem. Basically, the problem asks if it’s possible to design a system that can take any logical or mathematical statement and decide if it’s true or not. Turing modified this and called it the Halting Problem. If a program halts, it ends. If it doesn’t it continues on an infinite loop. The primary question, then, of the Halting Problem is whether it’s possible to design a program that can read in another program and determine if the other program halts or not. Turing addresses this with what is essentially a more complicated version of the proof (by contradiction) Dr. Wagstaff outlined to the right. What this says is that if you assume that, like a Turing Machine, any program can be written as a number, and that you can write program H(p) that can read in any program and will return 1 or 0 if program p halts or does not halt, respectively. So then you define another program G(p) such that if program H(p) returns 0, then G(p) returns 0, and if H(p) returns something not zero, then G(p) goes into an infinite loop. Now, every machine can be written as a number, so G(G) is possible. And then the complicated part: G(G) takes action based on the output of H(G). If G does not halt, then H(G) returns 0, which would mean that G(G) would return 0. This is a contradiction because G does not halt, but returns 0 when presented with itself. Likewise, if G does halt, then H(G) returns 1, which would mean that G(G) would go into an infinite loop. This too is a contradiction, as G does not halt, but goes into an infinite loop. This means that the assumption that H(p) can be written is false. No such program is possible to write.

Moving on from complicated proofs, we looked at the reading from Diamond Age. We first went over some background on the passage to give it some context, and then went into the details of the passage. The main character, the girl, is playing a game with a “primer,” which the class likened to an iPad. Princess Nell is her character, and her character has been imprisoned by automatons. She then has to administer a Turing Test to determine if her captors are human or machine, as this will determine her method of escape. After learning that her captors are machines, she escapes to the top of the tower where she find the skeleton of the Duke of Turing. She reads his books and journals, complete with references to ‘bugs in the machine,’ and masters them. After learning how to write her own programs in the chains used to hold programs, she becomes the Duchess of Turing.  The passage mostly focused on the Turing Test, figuring out if her captors were human or not, but it does involve a Turing Machine that functions as the lock on her door. The numbers on the lock describe what state the machine is in, and with their help she was able to reverse engineer the lock by running different chains through the machine and seeing how the states changed.

There was also brief mention of the book Gödel, Escher, Bach: An Eternal Golden Braid by Douglas Hofstadter, which discusses knowledge, meaning, and thinking.

We then transitioned and watched a clip from the movie Breaking the Code, which is based on a play about Alan Turing. (Interestingly, this clip isn’t in the American cut of the film.)  The clip involves Turing explaining his work to someone reviewing it, and Turing basically explains what we were talking about for the first half of class. This person says that Turing’s paper is “baffling,” specifically pointing out the title. After a request to explain, Turing gives a very detailed and helpful explaination as to what a Turing Machine is for and how it relates to the Entsheidungs Problem. He explains that it is about trying to prove right from wrong, and in a review of the history of attempts at this he mentions someone to trying to break down everything in to pieces of pure logic. He notes that this, of course, failed, and attempts to analyze mathematical axioms led to new types of mathematics. He describes that Hilbert thought it was possible to have a fundamental system for mathematics, with consistency, completeness, and decidability. Turing then notes that Godel showed this was impossible, and that math is either inconsistent or incomplete. Turing realized that he would have to have a system of proving all mathematical statements past, present, and future for Hilbert to be correct, which is what his Turing Machine idea would be designed to do. He notes that, of course, a Turing Machine cannot do this.

Class then closed with the assignment for the next class.