## Ex Scriptura ### Or: In the Beginning was the Paper ### Or: The Formal Theory of Paper ### Or: A Subfield of Writing ### Or: How to make a mark ### Or: How to convince Gödel --- ## On Turing's eccentricities at Bletchley Park > _In the first week of June each year \[Turing\] would get a bad attack of hay fever, and he would cycle to the office wearing a service gas mask to screen the pollen. His bicycle had a fault: the chain would come off at regular intervals. Instead of having it mended he would count the number of times the pedals went round and would get off the bicycle in time to adjust the chain by hand._ > -Charles Petzold, The Annotated Turing ## On Turing and Joan Clarke, 1941 > _In the spring of 1941, Alan Turing made a proposal of marriage to Joan Clarke, one of the rare women at Bletchley Park who wasn’t relegated to a mindless clerical job. Joan Clarke had been studying mathematics at Cambridge when she was recruited for code-breaking. A few days after the proposal Turing confessed to her that he had “homosexual tendencies” but the engagement continued for several more months before he felt he had to call it off._ > -Charles Petzold, The Annotated Turing ## On Turing's 1942-43 mission and meetings at Bell Labs > _In November 1942, Turing was sent on a mission to Washington, D.C., to help coordinate code-breaking activities between England and the United States. Following that assignment, he spent the first two months of 1943 at Bell Laboratories, at the time located on West Street in New York City. There he met Harry Nyquist (1889-1976), who pioneered the theory of digital sampling, and Claude Elwood Shannon (1916-2001), whose paper “A Mathematical Theory of Communication” (1948) would found the field of information theory and introduce the word "bit" to the world._ > -Charles Petzold, The Annotated Turing --- > _We may now construct a machine to do the work of this computer._ > -Alan Turing, 1936 > _Let us now return to the analogy of the theoretical computing machines... It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine..._ > -Alan Turing, Lecture to the London Mathematieal Society, February 20th 1947 > _If it should turn out that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence I have ever encountered._ > -Howard Aiken 1956 0: Ok so, let's recap. Church comes up with Lambda Calculus. Gödel comes up with General Recursive Functions. Kleene proves the two systems are equivalent. And legend has it that when Gödel realized his system was equivalent to Church's Gödel says "Oh. Well then I guess mine was wrong." 1: Did that actually happen? 0: Not sure, but it's a good legend. 1: So how does Turing fit in to this? 0: Well Turing's work is what convinced Gödel. 1: Convinced him of what? 0: That the three of them had probably captured _all_ of computation in these definitions. 1: Damn, what year was this? 0: 1936. 1: That's insane. > Steve Kleene: We had done all this work before we heard of Turing. Turing's paper is also 1936. But a little later in 1936. But my impression is that Turing did it independently of knowing anything about what we were doing. 0: Yeah so Turing is over in England. Born in 1912 in the Paddington part of London where that famous bear is from. By this point he's 24 years old. Still an undergraduate. He's not aware of any of this work from Church, he may have known about Gödel. And he comes out with this paper as a 24 year old college kid that ends up convincing Gödel. ## The Beginning of the Paper ![[turing-1936-01.png]] ![[turing-1936-02.png]] ![[turing-1936-03.png]] ![[turing-1936-04.png]] ![[turing-1936-05.png]] ![[turing-1936-06.png]] ![[turing-1936-07.png]] ![[turing-1936-08.png]] 0: The $m$ stands for man. Or machine. I haven't decided yet. ![[turing-1936-09.png]] ![[turing-1936-10.png]] ![[turing-1936-11.png]] ![[turing-1936-12.png]] ![[turing-1936-13.png]] ![[turing-1936-14.png]] ![[turing-1936-15.png]] ![[turing-1936-16.png]] - `rip`, `stdout`, and `.data` - `rip`, `output.txt`, and `.data` + `.text` - Line we're executing, buffer we're writing our output to, and all variables in the address space. ![[turing-1936-17.png]] ![[turing-1936-18.png]] ![[turing-1936-19.png]] ![[turing-1936-20.png]] | The Program | | | | | | ---------------- | ----- | ---- | ----- | ---- | | if state is | b | c | e | f | | and symbol is | None | None | None | None | | then do this | P0, R | R | P1, R | R | | and set state to | c | e | f | b | | You Think | 💭 b | | | | | | | | | | -------------- | ---- | --- | --- | --- | --- | --- | --- | --- | --- | | You See | 👁️ | | | | | | | | | | Paper Contents | | | | | | | | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Do the action for the b state. | You Think | | 💭 c | | | | | | | | | -------------- | --- | ---- | --- | --- | --- | --- | --- | --- | --- | | You See | | 👁️ | | | | | | | | | Paper Contents | 0 | | | | | | | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Do the action for the c state. | You Think | | | 💭 e | | | | | | | | -------------- | --- | --- | ---- | --- | --- | --- | --- | --- | --- | | You See | | | 👁️ | | | | | | | | Paper Contents | 0 | | | | | | | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Do the action for the e state. | You Think | | | | 💭 f | | | | | | | -------------- | --- | --- | --- | ---- | --- | --- | --- | --- | --- | | You See | | | | 👁️ | | | | | | | Paper Contents | 0 | | 1 | | | | | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Do the action for the f state. | You Think | | | | | 💭 b | | | | | | -------------- | --- | --- | --- | --- | ---- | --- | --- | --- | --- | | You See | | | | | 👁️ | | | | | | Paper Contents | 0 | | 1 | | | | | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | After one loop, we're at at address 4, where the eye is. And we're back to the same "state" where we started. - The "state" doesn't include the state of the paper. - The "state" is just the letter $b$, $c$, $e$, or $f$. - In other words, the "state" is just what you think, not what you see. So at this point we do the same four things we just did, again. | You Think | | | | | | | | | 💭 b | | -------------- | --- | --- | --- | --- | --- | --- | --- | --- | ---- | | You See | | | | | | | | | 👁️ | | Paper Contents | 0 | | 1 | | 0 | | 1 | | | | Paper Address | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | So then we end up here, thinking about b again. Now do this again for the table at the top of page 5 of Turing's paper. ![[turing-1936-21.png]] ![[turing-1936-22.png]] 1: What's the ə? 0: Uh... 1: _(Waiting patiently.)_ 0: Ok so... 1: Wait you didn't answer my question. 0: Yes I did. 1: What? 0: The ə symbol is called "schwa." It's a letter from the International Phonetic Alphabet. It represents the "uh" sound. 1: Weird. Why is Turing using it here? TODO: Once we get to the əə example, start including excerpts from The Annotated Turing. 0: Not sure. Seems like a pretty irrational choice. But that's a sensible thing to do here. In this example he's showing we can compute an irrational number. 1: Sometimes I feel like you can rationalize anything... 0: Not this number! Look. $0010110111011110111110$ 1: What number is that? 0: I don't think it has a name. But it's: 0 0 1 0 11 0 111 0 1111 0 11111 0 111111 0 1111111 0 11111111 0 etc. 1: How do we know that's irrational? 0: Well, it's got a pattern which is why it's computable, but the pattern doesn't repeat in a simple-minded way like the number we computed above that just went 0 1 0 1 0 1 0 1 0 1 0 1 0 1... ![[turing-1936-23.png]] ![[turing-1936-24.png]] ![[turing-1936-25.png]] ![[turing-1936-26.png]] ![[turing-1936-27.png]] ![[turing-1936-28.png]] ![[turing-1936-29.png]] ![[turing-1936-30.png]] ![[turing-1936-31.png]] ![[turing-1936-32.png]] ![[turing-1936-33.png]] ![[turing-1936-34.png]] ![[turing-1936-35.png]] ![[turing-1936-36.png]] 0: This time we won't have blanks between the digits. Or bigits. ![[turing-1936-37.png]] 0: Ok pause here for a second. 1: What's up? 0: Head over to this file with me. goto: [[lost+found/5/2]]