## Ex Scriptura ### Or: Out of Writing ### Or: In the Beginning was the Paper ### Or: The Formal Theory of Paper ### Or: Squiggle completeness ### Or: How to make a mark ### Or: How to convince Gödel --- > Steve Kleene: Well as I say, I don't know how firmly convinced Gödel was that his General Recursive Functions represented all effectively calculable functions. > > Gerald Sacks: He seemed very skeptical. > > Steve Kleene: I think he was skeptical. And it may well be that Turing's presentation was what brought Gödel around. 0: So 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: [[2 - An Enumerable Infinity of Names]]