01:52 - Tom Stuart Introduction

02:24 - Understanding Computation by Tom Stuart

02:53 - Why Tom Wrote the Book

12:46 - Finite Automata

14:27 - Turing Machines

18:37 - Pages 187-192

• Types and Programming Languages by Benjamin C. Pierce

22:22 - Lambda Calculus

• The Halting Problem

35:36 - Decidability and Undecidability

46:12 - The Cyclic Tag System & Iota

52:40 - Understanding Computation

• DNA Computing

57:37 - The Goldbach Conjecture

01:02:52 - Finite State Machine

01:05:14 - The Impact of Quantum Computing

• Scott Aaronson
• Quantum Computing since Democritus by Scott Aaronson

01:07:25 - The Book and Rails

• html - RegEx match open tags except XHTML self-contained tags - Stack Overflow

01:16:41 - Using Ruby for the Book

01:23:59 - Struct

01:26:18 - Teaching Programming Habits

01:31:16 - What Makes a Good Language?

Next Week

Consulting vs Product Work with Adam Keys

Transcript

JAMES:  Alright. So, what are we talking about today? JOSH:  It’s hard to say. JAMES:  It’s hard to say. JOSH:  It’s undecidable. [Laughter][Hosting and bandwidth provided by the Blue Box Group. Check them out at BlueBox.net.] **[This episode is sponsored by JetBrains, makers of RubyMine. If you like having an IDE that provides great inline debugging tools, built-in version control, and intelligent code insight and refactorings, check out RubyMine by going to JetBrains.com/Ruby.] **[This podcast is sponsored by New Relic. To track and optimize your application performance, go to RubyRogues.com/NewRelic.] **[This episode is sponsored by Code Climate. Raise the visibility of quality within your team with Code Climate and start shipping better code faster. Try it free at RubyRogues.com/CodeClimate.]****CHUCK:  Hey everybody and welcome to episode 120 of the Ruby Rogues Podcast. This week on our panel, we have David Brady. DAVID:  All programs halt. Computer science is a fraud. CHUCK:  Josh Susser. JOSH:  My introduction is NP-complete. CHUCK:  James Edward Gray. JAMES:  I am made of lambda calculus. CHUCK:  And I’m Charles Max Wood from DevChat.TV. We have a special guest this week and that is Tom Stuart. TOM:  Hello from sunny London. JAMES:  That’s not true. I’ve been to London. DAVID: **What? [Laughter]**CHUCK:  I was going to say. JAMES:  I don’t buy that. TOM:  It is a beautiful day in London today. JAMES: **What? There were no beautiful days. I was there for half a month. [Chuckles]**TOM:  Got to plan ahead. CHUCK: **Yeah. [Laughter]CHUCK:  You have to be there. DAVID: [inaudible] doing a podcall.**JOSH: **Okay, let’s not do a podcast about weather. [Laughter]**JOSH:  How are you doing, Tom? TOM:  I’m good, thanks. How are you? JOSH:  Could use more sleep, but I’m feeling great. CHUCK:  Since you’re new to the show, Tom, do you want to introduce yourself really quickly? TOM:  Yeah. My name is Tom Stuart. I’m a Ruby on Rails developer and freelancer and I just wrote a book. I think that’s probably what we’re going to talk about today. CHUCK:  Probably. JAMES:  What’s that, you wrote a book? TOM:  Yeah. JOSH: **We could talk about the weather. [Chuckles]**TOM: **That would be the British thing to do, but I don’t want to impose myself on you. [Chuckles]**CHUCK:  Yeah. We’ll catch him on the other nice day that happens in London. JAMES:  Yeah, there are probably two. JOSH:  So, cool book. TOM:  Thanks. JOSH:  Tom, I’ve got to ask you. Why did you write this book? TOM:  Oh, wow. JAMES:  Can we say what the book is? JOSH: **Oh, that’s a great idea. [Chuckles] Go for it, James.JAMES:  Oh, it’s called ‘Understanding Computation’. Therefore, you read this book and then you understand computation. JOSH:  I like the subtitle, ‘From simple machines to impossible programs’. That’s like I feel every day. JAMES: [Laughs] Kind of is, yeah. Okay, back to the question. Tom, why did you write a book about understanding computation?**TOM:  Okay, well that’s a good question. The story’s long and boring, but there are two basic reasons why I wrote it. Firstly, it’s that I was a self-taught programmer as a kid. Then I did an undergraduate degree in Mathematics. And as part of that, I had to learn a load of difficult stuff that I didn’t find very easy. When I went on to be a graduate student in Computer Science, I found it extremely challenging to learn the things that I was supposed to learn. It was very difficult to internalize all of these ideas. When I was trying to learn, I was trying to do programming language research, I was trying to learn about compilers and programming language semantics and a lot of these sorts of computation theory and stuff like that. I found those things very difficult. It required a lot of miming. I would sit with textbooks for a really long time just frowning at them and looking at loads of mathematical notation and not really getting it. Then I would eventually get it. In the moment where I got it, I was simultaneously delighted by how cool it was and incredibly frustrated by how long it had taken me to get this cool idea into my head. At that point, I realized that there were interesting ideas that I wish I had already known about but that I’d never really felt would be accessible to me. The other thing was that as a graduate student, I was doing a lot of teaching of undergraduates and trying to explain stuff to them and I gave some lectures on optimizing compilers and stuff like that. I found that a really enjoyable experience. Because, it’s going to be cliché, but I found that trying to explain things to people really help me to clarify my own understanding of them. And sitting down with some smart people and trying to get them to trying to communicate ideas to them in a way that was clear and made sense really forced me to get everything straight in my head and figure out what all the dependencies were and really plug the ideas together in a way that made sense to me, so I could communicate them to someone else. Those were the two main things that conspired in my head. This was about a decade ago that those things happened. And at that moment, I remember thinking, “I really should write down all of these things that I think are cool in a way that I can communicate them to people that don’t have all of the mathematical prerequisites to understand them.” And it’s just been stewing away in the back of my head all that time until 2011. I gave a talk at a conference called Ruby Manor in London where I talked about the lambda calculus. That went down pretty well. People seemed to enjoy it, much to my surprise really. I talked about it mostly as a joke. It was sort of a troll. But people seemed to really enjoy it. I did a load of lambda calculus stuff in Ruby and when I wrote it up and put it online with the video, a lot of people were excited about it. As a result of that, I ended up having a conversation with O’Reilly who were enthusiastic about turning it into a book. Then I disappeared into a hole for a year and typed. Then when I came out of the hole, I had a book. So, that’s pretty much the whole story. JAMES:  That’s awesome. DAVID:  That’s awesome. JAMES:  There is a really great quote in the book that mirrors what you just said and it’s in the introduction. It says, “If you’re interested in the mind-expanding parts of computer science that deal with programs, languages, and machines but are discouraged by the mathematical language that’s often used to explain them, this book is for you.” And in my opinion, that is dead on about what this book is. It was really good. TOM:  That’s great. DAVID: **And then you follow it on page 22 with a full-page troll. [Laughter]**DAVID:  Which are the inference rules in a mathematical notation I can’t even read. JAMES:  Yeah, I threw the book across the room at that point. DAVID:  The number of trolls in this book is great. JAMES:  Yes. JOSH: **David, you just need your reading glasses for that page. [Laughter]**TOM: **I thought it was really important to ease people into it. You’ve got to start with the easy stuff and then psych yourself up because it’s going to get a lot more difficult later. [Laughter]**CHUCK:  I do want to point out, when I was reading it, it was really interesting because in a lot of ways, it was like, “I knew this stuff but I never could have explained it this way.” I was a computer engineering major in college. You get that blend between engineering math and computer science, the way that you build up your proofs. In some cases, it’s like, “Look, there’s a whole bunch of uninteresting or whatever math,” that we’re not going to do here, but just walking through it. I remember designing finite automata in school and fighting through some of these concepts. They give you the mathematical explanation of what it is and why. I don’t think I’ve ever seen as clear an explanation of what all of these things are and why they’re important. TOM:  Oh, that’s great. Part of my hypothesis with this book, I have a crazy wall where I’ve written down all of the ideas that I had in my head that made me want to write this book. I was very careful to not actually put any of it into the book. I assumed that anyone reading this book is not directly interested in what I’m trying to do. They just want to see the thing. But specifically, one of the things, one of the ideas I wanted to test out by writing this book is the idea that in order to explain anything of a reasonable level of complexity, you have to rely on something. This is a thing that Richard Feynman would talk about, that you have to have some kind of basis for understanding before you can explain something more complicated. If you’re going to try to fully explain anything, even something quite simple, and you’re going to try and go all the way down to the bottom, then your explanation is just never going to finish. So, you have to have some kind of cutoff point. It occurred to me that there are lots of things in computer science and specifically in computation theory that I think are really interesting. Always, quite a small thing that sits on top of a gigantic tower of mathematical prerequisites. And actually, a lot of those things could just as easily be sat on top of something else, which is the huge amount of intuition and knowledge that you have as a computer programmer that if you’re self-taught, then there are loads of things that you intuitively understand that maybe you’ve never even sat down and thought about but you’ve just internalized them by the process of learning to program computers and feeling what it’s like to talk to a computer all the time and things. So, an example of that is the proof of the undecidability of the halting problem is usually presented in very mathematical language and it depends on quite a high level of mathematical sophistication. It just assumes that you’re happy with the idea of things like functions, mathematical functions. The proof of that usually talks about stuff in terms of Gödel numberings. There’s this idea that you can effectively enumerate all of the computable functions. You can associate each function with a number and that number encodes the way that that function is computed and stuff like that. And that’s mathematically quite a complicated idea to get your head around. A lot of these proofs talk about manipulations on these Gödel numbers of functions and stuff like that. That’s one of the things that when I was trying to explain it to undergraduates a decade ago. I just thought, “Well, this is essentially exactly the same idea as the source code of a program.” If you find someone who knows what source code is and when you have a program, it’s the thing that you can run and when you run it does something. But before you run it, there’s this thing called the source of the program, which is effectively just a giant number. It’s a sequence of bytes that’s written on the disk. And I sort of realized that you could just refactor the whole explanation and swap out all of the prerequisites that were mathematical and just think, “Well, what are the things that a smart, self-taught programmer is going to understand and how can I reconfigure this explanation in terms of stuff they already know?” So, I hoped that the experience that some people will have is that they read through this stuff and they hopefully never hit up against a wall of seeing something that they just can’t get. Because I think the problem with mathematical explanations of things is that if you’re sitting there staring at the page and there’s a bunch of symbols there and you don’t understand what they mean, then there’s not really anything that you can do about it. You just have to not understand it. Whereas my hope is that by explaining things with code, and with ideas, not too sophisticated ideas like the idea that a program has source code, it’s something that firstly, you don’t trip over in the first place because you just get it, and secondly, if there are details of the explanation that you trip over, then I’ve given you a bunch of code that you can run as well. So if it means that you have to stop and type in all of that code or clone it from GitHub and poke at it for a few hours until you’ve built an intuition about it, then hopefully you have crossed that hurdle and now you can continue and enjoy the rest of the book. So I’m hoping there aren’t too many sticking points like that and that I’ve managed to anticipate the moments where people are going to need that little nudge of familiarity of, “Oh remember this thing that you recognize from all those times you’ve written computer programs? Now we’re going to use that idea as part of something you haven’t seen before but hopefully you’re not going to have to make too many mental leaps in order to understand it.” JAMES:  I want to talk about what Tom just said there a little bit for our listeners, because it really turns out to be the thing in this book that makes it so cool. So you have this, aside from the page of math troll that David brought up which is just absolutely hilarious, Tom just takes simple programs and teaches you these fundamental concepts of computing using just simple programs layered on top of each other. So literally, you look at this book and you think, “Oh, it’s going to get into discrete finite automaton. Is this something I can handle?” and the answer is truly, “Yeah, you absolutely can.” You can totally handle this. JOSH: **Okay, so there’s a really brilliant thing that I saw in the book, and Tom, there were a lot of brilliant things, but the thing that really made me, my first jaw-dropping moment, was when you’re explaining how one of those finite automata worked and the example that you showed was, “Oh, here’s how you parse a formal language.” [Chuckles]**JAMES:  Yes. CHUCK:  Yeah. JOSH: **It was like you were tricking your readers into learning two complicated things by explaining one in terms of the other. [Laughter]**JOSH:  At the same time. It was great. TOM:  You have to be a certain kind of person to find that stuff interesting. But I’m hoping that enough of that kind of person will get to that part of the book and be like, “Yes! Pausing.” DAVID: **I went to the keyboard so many times to write Ruby. Halfway through the book, I realized, “Son of a gun. You explained the concept of denotational semantics, which is where you explain one concept in another language.” And then your whole book is explaining computer science in terms of Ruby code. [Laughter]**CHUCK:  Well that was the thing that I thought was so interesting too, was that all of these things, all the way up through a Turing machine, they’re all theoretical constructs. They don’t actually exist anywhere. They really can’t. But you get this working code that basically simulates it. That was what blew my mind. It was just, “Yeah, these are concepts that you understand.” They’re theoretical. You’ll never see on out in the wild. Then it’s like, “Yeah, but there’s code that basically makes it happen.” It’s just like, “Whoa. Okay.” JOSH:  Okay. So my freshman year of college, I’m going to Caltech taking CS 10 and being taught by Carver Mead which was the most amazing thing, to have CS 10 taught by someone like Carver. But he came out in one of the early classes with a physical Turing machine. It was this mechanical contraption that had a big board that looked like one of those old telephone switchboards where you would plug cables in to the holes and to connect spots on the board. That was how you programmed the state machine for the state transitions. Then there was this other contraption connected to it that was the tape. There was this big mechanical tray that would slide back and forth as the head would come down and mechanically slide the section of the tape front or back. And he programmed the thing to solve and then reprogrammed it. And we got to watch the Turing machine execute different programs. DAVID: **Yeah, but have they ported the Unreal engine to it yet? [Laughter]**JAMES: **That’s actually, Tom talks about this a little bit about how computation is pretty much just what can we work out with a pencil and a piece of paper? Only now, we let computers do it and we can do a lot more. But there are lots of old examples. I think there’s one using matches and matchboxes. It was this old system build. I want to say the 1930’s, but don’t quote me on that. I can’t remember who did it either. But it was like a tic-tac-toe solver using these matchboxes and stuff. Oh sorry, Tom, that’s noughts and crosses. [Chuckles]**TOM:  Thank you. JAMES:  But anyways, it was this solver just using these simple bits. So computation was definitely happening before computers and such. JOSH: **Okay. So the other awesome thing about this book is it’s the first thing that I’ve read in years that uses the phrase ‘begs the question’ correctly. [Laughter]**JAMES:  Yes, that’s right. TOM: **That’s a special little thing for anyone who, any pedants in the audience, that was a little shout-out. [Laughter]**JOSH:  It’s nice that he thought of -- CHUCK:  He actually has something to say to that. It’s great. TOM:  **You know, writing this book was extremely painful. I was really psyched about doing it. When I got the contract from O’Reilly, I was really happy and I had a huge amount of enthusiasm and energy for it because this is something I am genuinely really passionate about. We literally could talk about this all day so we just have to cut it off at some point. But I love this stuff. I love talking about it to anyone, regardless of whether they’re interested. I don’t know. It’s really difficult to not just keep talking about it and keep thinking about it. But then once I got into the process of actually having to write a book about it, that completely reconfigured my understanding of it and it completely changed my relationship with the material because it just became my enemy. Every morning I would wake up and I’d go and sit in front of the text editor and it would be like the blinking cursor of death and I would not know what to write. So to get myself through that process, I just had to put a bunch of stuff in that made me feel like I was enjoying myself and the people who were reading it would actually have a little moment of satisfaction. So the little pieces like that were I’m like, “Yeah, I am actually going to use ‘begs the question’ correctly,” that gave me a tiny amount of satisfaction and I enjoyed imagining that there was someone else who would get a tiny amount of satisfaction .and also, some of the examples like some of the numbers I choose or some of the quotes that I choose to illustrate things or whatever are really not pursuant to the actual explanation. They’re just about me. There are those little moments of me trying to retain my sanity. It’s like when you get a fortune cookie and you open it and it’s got the, “Help, I’m trapped in a fortune cookie factory” fortune inside. It’s like that. [Chuckles]JAMES:  The Carl Sagan quote brought a smile to my face. That’s my favorite Carl Sagan quote. JOSH:  Yes. And then of course there were pages 187-192. TOM:  Right. JAMES:  Which is beyond amazing. JOSH: [Laughter]**JAMES:  I got there and just cracked up. It was great. JOSH:  Okay, so for everyone playing along at home, it’s basically over four pages of impenetrably unreadable lambda calculus. That was my first impression when I looked at it. But Tom, I’ve got to say that after having read through everything up to that point, I can look at that code and I can actually understand some of what’s going on there. TOM:  Wow, that’s great. DAVID: **Tom, are you aware that there’s a typo on page 191? [Laughter]**TOM: **Don’t you dare. So firstly, don’t you dare. [Laughter]**DAVID:  I typed this program in and it was no fun. TOM: **Well, that is an excellent troll. However, another coping strategy that I had as part of writing this book was that I just went off on massive displacement activities. One of the largest displacement activities was, one of my favorite books when I was trying to learn graduate computer science is a book called ‘Types and Programming Languages’ by Benjamin Pierce and it’s this amazing textbook about type systems and I highly recommend it to anyone who’s interested in this kind of thing. But it has code in it that is evaluated. So all of the console sessions in that code, I think the output has been generated by a computer program. So he wrote this book and then he made sure that all of the output that you’re seeing from the example programs in it was actually real. And I thought, “Wow, that’s a good idea,” because it’s fairly likely that when I’m writing this book, firstly there’s going to be a whole load of console sessions in it. And secondly, it’s also likely that I’m going to want to go back and change the code that’s in the book. And the prospect of going and editing the name of a class, for example, and then having to grep through all of the DocBook xml to find all of the places where I mentioned that class name and check that they were correct just filled me with a Lovecraftian terror. So what I did instead was the potentially much worse thing of writing a tool that used Nakagiri to slurp in all of the DocBook xml and then find all of the xml elements. Fortunately, there is a DocBook xml element that means this is code that is being typed in on a console, so with XPath I could find every single one of those and then I could eval all of that code and then capture the output into a StringIO object and then paste that in automatically after it in the book. So I did have a cycle where as I was writing those chapters, I would just be typing in the input to IRB and then I would run it through this tool and all of the output would automatically inserted into the book and then I would tinker with it a bit and insert whitespace and stuff. And also, I could insert ellipses and then when I re-ran it, it became a test suite. When there was already output there, it would just diff the output that it actually got against the output that was already inserted into the book. And if it was the same modulo whitespace and ellipses and stuff, my test would be green. So I know for a fact that all of the code in that book actually works. So you cannot troll me. [Laughter]**JAMES:  I must say, something like that would almost be required for this book because the book was defining its own programming language by page 23. Keeping it all straight and stuff, there was so much room for error. I was incredibly surprised by it. Every time I read a programming book I find some little thing that, “Oh, that’s wrong,” or whatever. But not this time. I can’t point to any of the code and say, “That’s wrong.” DAVID: **Do you regret that the book, once it’s in dead tree form, cannot modify its own code and is therefore decidable? [Laughter]**TOM: **Yeah, that’s very disappointing. In fact, we’re all laughing here, but there is a serious point to be made which is that it is actually quite difficult to explain stuff non-interactively. And I initially, when I pitched this book to O’Reilly, I wrote an outline, a chapter plan, that had a lot more stuff in it than was actually in the book. A lot of that isn’t in the book because when I sat down and tried to explain it, I just found that the constraints of a static text on the page book that you can’t interact with was just not good enough to be able to build a meaningful explanation and to instantiate that problem. I had a whole chapter that was just going to be about, after the programming with nothing chapter which is the stuff that introduces the lambda calculus, the chapter split into two parts. It’s got the impersonating the lambda calculus in Ruby which is just using procs and pretending that you’re programming in the lambda calculus and just using restrain to not rely on any other features of Ruby. And then there’s the second half of that chapter which actually gives you an operational semantics for the lambda calculus implemented in Ruby so you can write lambda calculus programs and then parse them and then evaluate their abstract syntax trees in Ruby. And that’s all fine, but I wanted to have another chapter after that which was about all of the different ways of evaluating the lambda calculus. Because in that chapter I don’t even talk about the fact that there are lots of evaluation strategies for the lambda calculus and they all have different tradeoffs and they have different termination behavior and different normalization behavior and all of these things that I think are super interesting. I sat down and I tried to write that chapter and I just found that it was too hard to do it without being able to show evaluation. In various places in the book, one of the reasons why I wanted to show small-step evaluation to Ruby programmers is that I thought that they perhaps have not seen programs evaluating by gradually boiling down. You just get used to when you run a Ruby program you just get the output. You don’t get to see all of the intermediate stages. So I thought it’d be fun to show that. But that was not really good enough to be able to explain, “Let’s look at these four different ways of evaluating a lambda calculus expression. Let’s see what their behavior over time is like. Let’s see how they differ,” and stuff like that. In an attempt to explain all of that, I sat down and made a little interpreter, I did it in JavaScript and html, I made a little webpage where I could type lambda calculus expressions in and they would be parsed. Then I could click on different reduction expressions inside the lambda calculus expression and have it do a trace down the page that showed you all of the steps of evaluation. I was like, “This is excellent. This is exactly what I want to do.” What I want is for them to be able to click on stuff and feel all of the different ways, all of the different decisions you have to make as a person about what you’re going to click on next. Then I could explain the evaluation strategies in terms of that. But I just couldn’t find a way to freeze that onto the page. So I feel like although it feels amazing to have got this book out of my system and to not have to think about it anymore, it still feels like there’s a load of stuff like that that I wish I could have gone into more detail on that’s still lodged in my brain somewhere and I haven’t quite got out into the world. So I don’t know what to do about that. I think I might just change career. [Laughter]**DAVID: **I like the fact that you explained that there is that problem. And you actually have the sentence of “This sentence is false.” And you’re explaining that that sentence refers to itself. You can’t have that paradox without the word ‘this’ in that sentence, the self-referentiality. I could see how trying to scale that up might be a little tricky. Having a chapter that ends in, “By the way, this chapter is false,” that might be too much of a troll. [Chuckles]**JAMES:  I want touch on what you two are talking about right there. But I’m worried that people listening to this episode are thinking, “Oh, they said this super readable and now they just keep using words like lambda calculus.” But it’s so hard to convey how understandable he made these topics. The halting problem is a great example. Tom talked earlier about how it’s usually explained with this horrible, horrible math and it’s very, very complicated. He wrote a simple program that basically takes the input of some program and then returns if it halts or doesn’t halt. It’s totally something you can understand. He walks you through it step by step. It’s super easy. Then once you get that far, it’s so easy to see why that actually can’t work in every case. Then he walks you through, step by step, why it can’t work in every case. So you gain this fundamental understanding of the halting problem and by extension, what computers cannot do using just the most straightforward no math, you can see it right there, why it can’t work thing. That, I just cannot stress enough, is what makes this book amazing. CHUCK: **Yeah, he also in the same manner proved that he will never be a good professor at a college because he explained it so well. [Laughter]**DAVID:  I want to second James’s comment that we’re talking big stuff here but this book literally got inside my head. I had a dream two nights ago. JOSH:  Literally? CHUCK:  Did it fit? TOM:  Whoa. DAVID: **Oh, that’s true. The book literally got inside my head. [Laughter]**DAVID:  Yes, the book figuratively got in my head. The knowledge from the book literally got inside my head in unexpected ways. Because I had a dream that woke me up laughing because I wrote a halting checker that trapped Ctrl+C and returned, “Yes. It halts.” So you run it and it runs forever and eventually you say, “No, okay. Just kill this program.” And then the program says, “Yes. It halts.” SIGINT return yes, and it woke me up laughing. JAMES: **There is a downside to this book. I’ll give a totally straightforward downside. I read tons of programming books, especially for this podcast, we read one all the time, to the point where I’ve read enough of them that I can just fly through them for the most part. This book is not that. I picked it up and 20 pages into it, I slowed to a crawl because I realized, “Oh, I’m going to have to think here and I’m going to have to work through this.” This is probably one of the most ‘best read with your text editor open’ books. You will want to be putting some stuff in to IRB and playing with it and things like that. You actually will be gaining this understanding. I think all of us Rogues ran into it because you know, we’re terrible procrastinators and we’re like, “Oh, week before the book club episode, we should fire it up.” But we all got into it a little early and started giving each other warning flags, “Mayday. You cannot read this in two days,” kind of thing. [Laughter]**CHUCK:  Yeah. JAMES:  And it’s very true. I literally had to ask my wife, “I just need a week off so I can sit down with this book and figure it out.” And that really is pretty much what it takes. But it’s so worth it and engaging. You’re having so much fun when you’re playing with it in your editor and stuff like that. That’s what makes it awesome. TOM:  I’m really glad you feel like that because it was that, I’m ripping myself because I already said this, but it was that kind of interactive element to it that I felt was really important. I didn’t want people to feel that they had to hang on every word that I was writing because quite a lot of the time these ideas are fundamentally difficult to explain concisely in English. Because there are so many things you’re trying to refer to. I was again literally having problems with pronouns. I was writing sentences where I wanted there to be three different this’s that I could refer to. You can get tangled up in knots. A lot of me writing this book was just constantly writing and then deleting paragraphs that were just gibberish. In the end, my solution to that problem was just to relax a little bit and think, “Well I’ll just type what I want to say.” If I was just talking to someone in the pub and they said, “So, what’s the big deal about the lambda calculus?” or, “What is abstract interpretation?” or, “What is the halting problem?” or whatever. I just wrote what I would like to say in as conversational a style as I was able to write it then just allowed the code to be the crutch that I was leaning on. And whether that’s good or bad is probably a matter of opinion. But I was hoping that by having all of that code there, because different people will have different difficulties with different topics. I’m aware that probably nobody will read this book and not already know something in there. Everyone who has done any computer science, or even someone who is just a Rails programmer and who has worked on a medium-sized web app, will probably know about state machines for example. Those people are going to be able to breeze through that stuff. So for me to really laboriously explain that in lots of detail would probably just be quite boring. I was trying to go through it as quickly and I suppose, like James is saying, as densely as possible and just throwing out the code there. Again, the subtext on my crazy wall was like, “Well if you hit a page where you feel like you’re not really getting it, then just stop there, fire up your text editor, and just play around until you feel confident enough to continue.” JAMES:  That’s awesome because, like in the lambda calculus example, if you sit down and work through that in IRB, there’s no way you can get to the other side of that and not understand recursion. If you don’t get recursion, then that is the example for you. That will do it. JOSH:  I still have no idea what the S combinator is though. CHUCK: **That’s another book. [Laughter]**CHUCK:  The thing that I think is so interesting though is that just with my background, I keep bringing this up, but all of my computer science classes in college, they just hand-waved over this stuff. It was the engineering classes that were the ones that really hit home on a lot of this stuff because this is how you think about really designing the machines to handle these problems. So it was just fascinating to me to get to read through it and see it from the perspective of software. It really did cement a lot of the stuff that I didn’t understand for me. TOM:  I think there is interesting stuff there of practical value. I’m conscious that there is not very much practical value in this book other than satisfying the curiosity or people who are interested in these things. But I think there are -- DAVID:  I strongly disagree. TOM: **Okay. Well what I was going to say is that things like regular expressions. If you say it to someone who is a self-taught Ruby programmer, do you understand how regular expressions work? They’ll be like, “Yeah, sure. You’ve got your dot and you’ve got your asterisk and you’ve got your question mark.” And then you’re like, “Well I’m going to stop you there, because have you ever thought about how it would actually work?” [Laughter]**TOM:  What’s going on there? So that was one of the places where I wanted to, and I suppose with the parsing stuff and the programming language semantics as well actually, I just wanted to scratch at these little things in people’s understanding where it’s like, “Well you’re using this stuff all the time. You write computer programs every day, or you use regular expressions every day, or you use parsers every day, without even thinking about it. But what is actually going on there?” If I put you in an interrogation situation and said to you, “Can you explain to me what’s going on here?” where would your explanation bottom out at just hand-waving and shrugging? I just really wanted to just needle those points a little bit. It sounds like an excellent retort is coming back about what the practical value of that is, but for me, the real value of this stuff is this is what keeps me sane and what makes me excited about being a programmer. Because the reality of being, when you work as a computer programmer, it’s brilliant because effectively someone is paying you to do the thing that, well in my case, what I would be doing anyway. So it feels like an amazing hack to actually have people who are prepared to give you money. But the consequence of that is that you end up doing a lot of stuff which in the day to day is maybe not that fascinating. Maybe you’re building another CMS in Rails or whatever. It’s tempting to let your shoulders droop a bit and to say, “Oh man, it’s another day at the office and I’m just hacking away like a code monkey.” But it’s the fact that I have this slightly unhealthy fascination with the way it all works and the way it all fits together and the interface between this stuff, the metaphysical aspects of what’s going on in the universe, that’s what keeps me excited. That’s why I really love writing computer programs. It’s really important for me to be able to remind myself. And I think I say this right at the end of the book as well. You’re kind of doing magic, amazing magic stuff, and it’s really easy to forget how magical and amazing this stuff is. So if you just sit down and think about it and you can rediscover this awe of how amazing all of this, that this is possible even and that you can make a machine that will do whatever you want it to do, it’s super exciting. That’s what I want to try and retain a little bit of as I get older and more jaded. DAVID:  Can I ask you a question that I think will show you the practical value of this book? TOM:  Sure. DAVID: **Okay. So it’s a long question and it’s going to be a complicated answer, not that it’s been hard to get words out of you. [Laughter]**DAVID:  But I need you, for the readers, to give a short explanation of decidability and undecidability. Then here’s the question. How much does undecidability correlate with technical debt and our inability to understand or test code? Because that was a huge takeaway for me from this book. TOM: **Wow. Okay. My brain is churning. [Laughter]**TOM:  So a short explanation of decidability. Think about a subset of all the problems we might want to solve with computers. There are certain kinds of problems which is called decision problems. A decision problem is where we just want to ask a computer a question to which the answer is yes or no. So this is like a predicate method that you would write in Ruby. You want to know, read in an integer and tell me is it even, yes or no. So these problems are called decision problems. And decidability is the issue of whether one of these decision problems is effectively always answerable. That particular question of whether a number is even is decidable, because for any number that you feed into a computer, it’s possible I’m being extremely vague here, but you can write a program in Ruby that will tell you whether a number is even or not. That decision problem is decidable. I go into some detail in the book to explain that there are other kinds of problems that are not decidable in that way. Some of those problems, to get onto the actual substance of your question, some of those problems are unfortunately problems that we would really like to be decidable. So this is something that, again, was never quite, when you read textbooks about computation theory, I feel like they go 90% of the way to the exciting point. And the 90% is like, “Here’s a load of mathematical prerequisites. We’re going to talk about Gödel numbering and we’re going to talk about Gödel’s first and second incompleteness theorem and all of this stuff and formal logics and arithmetic and all of this kind of stuff.” And you get this amazing result at the end about the existence of undecidable problems. Then they stop as if you get it now. Like, “Okay, we’ve showed you a mathematical result. So there you have it.” I think even when people are taught this in a more practical setting, people who do understand how the halting problem applies to computer programs, I expect if you were to grab a random Ruby programmer and say, “Can you summarize what’s the deal with the halting problem? What does it mean that the halting problem is undecidable?” They’ll probably say, “Well, you can’t write a computer program that will tell you for sure whether or not a computer program is ever going to finish executing or not.” And you’re like, “Well okay. But so what? What’s the last step of this? Why do we care?” Is that just a stupid academic result? It doesn’t sound like something that’s going to have any consequences for me. I write web interfaces to databases. I do not write programs that tell me whether other programs are ever going to halt or not. It’s very easy to get into this mindset of even if you’ve understood it maybe you haven’t internalized the consequences of it. One of the things that try in a small way to explain in the book is that this is actually massively relevant. This is why our lives are so painful. Because the halting problem, there are lots of other problems that are reducible to the halting problem that we really want to be able to solve. Things like, does this program satisfy its specification? Does this program have any bugs in it? Does this program make any private API calls? All of these kinds of things that us or Apple or someone else in the world might want to tell. Basically, and this is the depressing conclusion that I come to in that chapter on decidability, is basically anything that you want to know that is interesting about a computer program, in general, is undecidable. It may well be the case that in the vast majority of cases, it actually is decidable but there’s always going to be this bit of grit. There’s always going to be this fly in the ointment which is like, “There are always going to be programs that you want to ask questions about for which these decision problems are not answerable.” So even if you think you have written a program that can tell me whether my program is going to run out of memory or whether it’s going to segfault or whether it makes a particular API call or not, I will always be able to cook up a program that when I feed it to your decider, it gives the wrong answer. That’s pretty depressing. JOSH: **This is sort of the quantum uncertainty equivalent in computation. You do quantum mechanics, you’re like, “Okay, I can’t actually know the universe down to the specifics of everything.” What you’re saying, I’m going to have to go back and listen to the recording several times to actually digest everything you just said. [Laughter]**TOM:  Sorry. JOSH: **Like you said, there are some real world implications and I think that understanding that is really valuable. I remember early in my career, interviewing at a company that was building what they used to call specification systems. And for Ruby developers, we use test-unit or rspec to write tests to tell us something about how our code is operating. If we’ve done a good job, then we have some confidence that we know what’s going on in our code and that it’s behaving correctly for some definition of correct. People who focus on these ways to describe code, they end up in this black hole of naval-gazing where it’s like, “Okay, I just keep making my specifications more and more powerful to describe what’s going on in the code.” Then somebody has the bright idea of, “Well, if my specification language is so powerful that I can describe everything that’s going on in my code, after I’ve written the specifications, I could use that to generate the code or I could just execute the specifications.” Then you’re back where you started, is the problem. [Laughter]**JOSH:  Because now you have a specification system that it’s the Turing equivalence going on there where the specification has all of the power of the language that it’s describing, which means that it has all the same limitations, if you look at it the other way. Then you run into all the same problems. How do you prove that the specifications you wrote are correct? TOM:  Yeah. I think there are a load of, again going back to my crazy wall, I think there are a load of points that I wanted to bring out which are maybe to do with preconceptions that people have, or misconceptions I suppose is what I mean, about what’s possible and what’s worthwhile. So yeah, one of them is there are a large number of undecidable problems concerned with what programs are going to do. This is fundamentally important that people who work with computers have some understanding of this and understanding the scope of the problem as well. They don’t think it’s only writing programs that tell you whether other programs halt that is the problem. That actually, that is the crack through which a million other problems are leaking all the time. So this is why it’s important for engineering students to understand the laws of thermodynamics so they don’t spend their whole career trying to build perpetual motion machines. If you can just be sat down and explained in a way that convinces you that you cannot build a perpetual motion machine, then you have just freed yourself from a whole load of pain. You don’t want to go down that rabbit hole. Some other things I wanted to bring out, and again I don’t think I did it particularly well or certainly not explicitly, was just we spend a lot of time, particularly in the Ruby community and in related communities, worrying about our tools and in some cases arguing over what’s better, is Python better than Ruby or whatever. Obviously, some programming languages are more powerful than other programming language and we have these twin ideas. But firstly, in order to do useful computational work, you have to have a complex system that is difficult to learn and difficult to understand and a gravy train that you can get on and conferences that you can go to. That’s what computation means. Secondly, that there are different levels on that spectrum. There are more complicated and more powerful programming languages. Obviously, in some ways that is true and it depends on your definition of power and stuff like that. But I also really wanted to pour water on that a little bit and in having that chapter that was about the lambda calculus and also the chapter about universal systems which was one of the two things I really wanted to write about. The whole book is basically a giant yak-shaving exercise for me to be able to talk about universality and how pervasive it is and how little it depends on. I really wanted to write that stuff about cyclic tag systems and rule 110 and stuff like that, and the SKI calculus and stuff. I just wanted to show how simple these systems can be and still get full-blown exactly as much power as you get from your programming language or from Haskell or from whatever awesome programming language it is that you think is the best programming language. At the same time, I wanted to slightly deflate this idea that it massively matters which language you choose. Or rather, that your reasons for choosing a programming language needs to be wider than just what computations is it capable of doing and you need to pay attention to things like what’s the community like and how good are the podcasts and how good is the ecosystem of tools and libraries available for this language. Because ultimately, that’s all you’re deciding on. Or how much do I like the syntax? Because none of this stuff really matters, particularly to the computer, it doesn’t matter. It doesn’t matter whether Rails is implemented in Ruby or implemented as the input to a cyclic tag system. It can perform the same calculations, possibly slightly slower, but still you’ve got the same capability there. Actually, that capability doesn’t rest on anything very complicated. When you look at that stuff in the universality chapter and you see just how simple some of those systems are, that is a thing that blew my mind when I first learned that I was possible to embed a Turing machine in something that’s radically simpler than a Turing machine. That was a real eye-opener for me and it makes me feel differently about programming computers and choosing languages and engaging in those kinds of unproductive arguments with people I suppose. JOSH: **So speaking of unproductive arguments, [Laughter]**JOSH:  You said what was it, the cyclic tag system? TOM:  Yeah. JOSH:  I think that blew my mind more than any of the other stuff that I read. Well, okay, actually iota blew my mind more than the cyclic tag system. But they’re both very similar in that they really reduce this complex system into something that is probably of equal complexity but it’s built of simpler and simpler parts. The book seemed like it was a walk down the path toward shifting complexity around. You say we’re going to come down to the smallest pieces that we can define that interact in ways that will create these results. So I looked at that iota combinator and that iota language based on it. I was like, “Where the hell does the complexity live in these programs?” I guess iota has two things. There’s basically whether you’re pushing or popping into the parentheses stack. So am I applying the iota to another iota or coming out of that application? And that’s all the information that you have to encode your program, is that relationship between successive applications of iotas. That seemed really similar or the cyclic tag system to me. You’ve really only got one bit of information that you’re using at each place. But it was just like, “Okay, so that’s really simple. But how do you start with pieces that are that simple?” And then it’s just the arranging of them that you get all the complexity that does all the magic. TOM:  I think it’s really cool that you said that. I’m really happy that you said that. Because this is again, something that I didn’t call out explicitly. What I wanted people to feel was that as you go down and you get to those simpler and simpler systems, you get to this point where they become more abstract in a way. And you get to the point where you’re having to think more and more about the encoding of things. In the sense that when you sit down and write a Ruby program or whatever, the Ruby interpreter is trying very, very hard and there’s a lot of complexity involved for it to talk to you in something which is in the grand scheme of things, extremely close to human language. The stuff that you’re having to type and the results that you see have been extensively massaged for your personal convenience. That is why the Ruby interpreter is a large and complicated piece of software, because the whole thing is designed to fit the human mind. The further down you go in that journey, down that path toward simpler and simpler systems, you realize that what you’re doing is uncovering the fact that that is going on. That actually, when you get to these simpler and simpler systems and you look at things like, even the lambda calculus is more than most people even want to look at. But the lambda calculus is a very sophisticated programming language in that it’s got something that intuitively we understand. It’s based on the notion of a function. Function abstraction and function application are ideas that we have had, effectively ideas from mathematics, and we are still reasonable comfortable with that. Once you’ve sat down and you’ve figured out how the Church encodings of the natural numbers and pairs and lists and all of the data structures you might want work, you can in a painful way, you can program in it. Especially if you do what I do in the programming nothing chapter, which is assign things to constants and say, “Well, I’m just going to have this giant lambda calculus expression that means increment,” then you are progressively recovering a language which is not massively different to Ruby. But when you get into those other systems like the calculi that I show and cyclic tag systems, they just become almost irretrievable alien. They don’t have anything. They don’t have any affordances in them that allow you to relax and feel comfortable and feel like you’re being catered to as a human brain. There’s something going on here and you can’t quite see what’s going on and it’s not making any attempts to help you understand what’s going on. But that doesn’t fundamentally alter the fact that it’s doing useful stuff. It’s just that it’s no longer doing useful stuff in a way that’s convenient for you. It’s all of that incidental complexity about accommodating your preferences and your biases as a warm-blooded mammal are no longer there. Now there’s just some kind of quite frightening thing happening where you can see these, when you run those things in IRB and you can see the iota expressions expanding and contracting and getting massive and then getting tiny again and things are boiling and combining, you get the answer out the end. You’re just like, “This is entirely outside of my experience as a human being, as a computer program.” There’s something going on here that isn’t for me that’s built into the universal, built into mathematics or something. For me, it was the realization that that is what Ruby and other user-friendly languages are tapping into. It’s like there’s something. It’s like the force or whatever. There’s something going on in the universe. And we can build this gigantic, I think there’s a bit in the book where I talk about this tower of abstractions and say that a computer is a device for maintaining this gigantic precarious tower of abstractions that allow us to, right at the very bottom of that tower is this raw power of computation happening in the universe. Then we have layers and layers of interpretation and encoding which when we layer those high enough, we get to something at the top where the encodings of things and the representations of things and the abstractions that things are expressed with are ones that we’re totally comfortable with. It’s just as you drill further down that stack, things get weirder and weirder until you get to the point where it’s really not clear what’s happening. My biggest fear with this book is that people are going to think that I’m some kind of expert on computation and they’re going to ask me really deep, philosophical questions about what computation is and how computation works and stuff. Because I’ve just got literally no idea. I haven’t got a clue what’s going on. It’s my fascination with the question of what the hell is going on that made me want to write a book about it. But I’m not any closer to an answer. If anything, I’m more confused than I was when I started. So sorry about that. JOSH:  So I have a real brain-melting question for you. And that’s have you considered that the human ability to understand computation in the realm that you describe in your book is at all related to the fact that we are somehow based on these strands of DNA that have these enzymes that can run up and down them and basically translate them into other strands of similar stuff? So it’s like a DNA strand is like a Turing machine tape. TOM:  Yeah. JAMES: **It is. [inaudible]**JOSH:  And you have these molecules that run up and down them and change the encoding and turn them into RNA and things like that. People have built computers or very simple computational devices out of DNA and enzymes. People talk about the brain as being the most powerful computational device known to man. At some level, DNA is an incredibly powerful computational device and the amount of stuff that we would have to simulate to actually get all of the capabilities of DNA and how it encodes and transforms information is huge. But there’s this model of computation exhibited by DNA and what we have with the Turing machine isn’t’ all that different from that. TOM: **No, that’s absolutely true. I think this is another example of a thing that everyone knows. Everyone who has a basic education knows about DNA and knows a little bit about how it’s encoded and the very, very rough details of what’s going on there. I learned that stuff when I was a kid. But it was a very lengthy process. You need to ingest that information properly and assimilate it and realize, there was definitely a moment where I was like, “Hold on.” Humans are digital. Just because we’re not binary doesn’t mean it’s not digital. Humans are not represented in an analog way. Inside an egg, there is not a tiny human waiting to grow. That is not how it works. There is actually a sequence of instructions that are written in a four-digit code that encodes all of the information necessary. That is a program which is going to evaluate on a biological computer. And the side-effect of the evaluation is going to be building a body and there’s going to be a human being. That is crazy. It might be overreaching to say that that is inherently related to our ability to understand or not understand these things. But I think that there is something going on which is that we are, well danger of venturing into non-scientific territory here, but my personal opinion is that we are just like hot wet Turing machines. That effectively, what is going on in your brain constitutes and astronomically complex ongoing massively parallel computation that is very difficult to understand. Personally, I don’t have very much faith that we’re ever going to be able to comprehensively understand it, to the extent that it’s possible to get a grip on that. It might just be, if you could completely reproduce the computational behavior of a brain, then maybe you would get something that works like a brain. But whether you’re any close to actually understanding how it works, I don’t know. But that’s one of the things that I think when I’ve talked about this undecidability stuff before and I spoke at the Scottish Ruby Conference about the undecidability of the halting problem and stuff like that, there were definitely people who came up to me afterwards and they were like, “What does this mean? What are you talking about? If my brain is just a computer, and computers are limited in what they’re able to do, then what does that mean for me?” So I think there are people who are keen or maybe the opposite of keen, but they perceive that there is a connection between all of this stuff and what is actually going on biologically and psychologically I suppose with humans. I am singularly unqualified to address any of those questions. Obviously. Nobody knows the answer to any of those things. Nobody really understands how the brain works. That question is very far from being settled. But it seems to me that the balance of evidence is such that it’s quite likely that what’s going on obviously, as you say in the cells of our body, I don’t think there’s very much dispute that yeah, that is just digital computation that is being evaluated on a wet computer. It feels to me as though that’s what’s going on in our skulls as well. I don’t really know how to process that or what the consequences of that are. I just want to cry now. I don’t know. [Laughter]**CHUCK:  You made him cry, Josh. JOSH:  I don’t know about you, but my brain is non-deterministic. TOM: **Yeah, sure it is. [Laughter]**TOM:  It definitely feels like that. DAVID:  Actually, I was going to ask you that. Why is it that I as a human being can look at a program that effectively boils down to, “This sentence is false.” How come I can look at a program like that and decide that it is undecidable when a Turing machine can’t? TOM:  Okay. Well that’s an interesting question. What you’re talking about there is you’re talking about having a specific program in front of you and making a decision about whether that program will halt or not. So in some cases you are able to do that for particular inputs. DAVID:  Ah, okay. In the general case, I can’t. TOM:  Yeah. So there are two reasons for that. Here are two examples of reasons for that. One of them is, I think in the book I talk about the Goldbach Conjecture. Because you can encode questions about arithmetic as a computer program, then any question in arithmetic can be expressed as a decision problem for a computer to solve. There are decision problems, the Goldbach Conjecture, we don’t know the answer. JOSH:  Tom, for people who haven’t read your book yet, can you define the Goldbach Conjecture for us? By the way, it’s one of my favorite conjectures. TOM:  Okay, sure. So the idea of the Goldbach Conjecture is this question of, the question is about whether every even number can be expressed as a sum of two prime numbers, so every even number greater than two. So is there any even number that cannot be expressed as a sum of two prime numbers, essentially. If you think, four is two plus two and six is three plus three and eight is three plus five and ten is three plus seven and so on. And you can keep going. And if you look at all of the even numbers, you can check, just by looking at all of the prime numbers that are less than that number and adding them together and seeing if they make that even number, you can figure out whether there are two prime numbers that add together to make it. It turns out, empirically, every even number that we’ve checked this for, that is the case. I can’t remember exactly how many we’ve checked. I think it’s up to, might be four quintillion. Is that right? JOSH:  It’s a lot. TOM:  Yes. A computer has sat down and exhaustively checked this for a large number of even numbers. So just based on the weight of evidence, it certainly seems like every even number greater than two is expressible as the sum of two prime numbers. But we don’t actually have a proof that this is the case. JAMES:  It’s the black swan thing. All we’ve seen so far are white swans but that doesn’t mean there’s no black swan. TOM: **Sure. So maybe there’s an astronomically large even number that is in fact not the sum of two primes. We don’t have a conclusive proof that that even number doesn’t exist. That’s really frustrating because it’s very easy to, and I go through this in the book, it’s very easy to write a program that checks this. So you can write a program that sit there checking the Goldbach conjecture for specific cases, checking it for four then for six then for eight and seeing whether there are two prime numbers that can add together to make that even number. That can keep going for as long as you like. If you set up that program such that it will finish if it ever finds an even number that is not the sum of two primes, and it keeps going forever, modulo available RAM and stuff on the computer, it will keep going forever if it never finds an even number that isn’t the sum of two primes. Then you’ve got yourself a program whose halting behavior is intimately connected to a problem in mathematics that we don’t know the answer to. So for that specific program, without getting into anything complicated or self-referential or metaphysical, I can just say if you look at that program, you can’t tell me whether that’s ever going to halt or not just because it’s a difficult question. But even beyond that, the stuff to do with the halting problem is not really related to that, or at least that’s not how it’s expressed. It’s more in terms of you can always, if you give me a program that you think decides the halting problem, I can use the source code of that program to build a new program that your program gives the wrong answer to. So there’s a self-referentiality thing, which is that you give me your [inaudible] halting checker then there’s a very simple transformation I can go through with that program to generate a program that will break your program. Then the analog of that for the question that you’re asking is you think that your brain is able to, say you think that your brain is able to decide the halting problem, in order for me to produce the canonical program that you can’t decide that for, I would need the source code of your brain and right now, we don’t know how to extract the source code of someone’s brain. Maybe at some point in the future, when the brain is comprehensively understood, we would actually be able to do that. I think that’s maybe the missing step, is the realization that whatever the program is that you’re running in your mind to make that decision, again this is a non-scientific claim, but I claim that that’s something that in principle, it is possible to write down in a way that we could feed that into your brain and then I could do the same transformation on that program and you wouldn’t be able to give the right answer. So I don’t know if that makes it clearer or less clear.**DAVID:  No, it does. The related question that I had was can a Turing machine with an infinite tape always decide a Turing machine with a finite tape? And it sounds like the answer is yes. TOM:  Yeah. If you’ve got a Turing machine with a finite tape, then that’s just a finite state machine. If you’ve got a finite tape, then there are by definition a finite number of states that that Turing machine could be in. Intuitively, the problem with the halting problem is that you never know whether the Turing machine is going to keep going forever. With finite state machines, or with push down automata, you can see when they go into a loop. Particularly, it’s easy to see with a finite state machine because the only state that it has is, I’m tripping over words again, but what state it’s in, if it’s in state one or state two or state three or whatever. You can always see, when you’re back in a state that you’ve already been in and the remaining input is the same as it was, you can say, “I’ve been in this situation before so I can see that this is just going to repeat over and over again. I’m just going to be stuck in an infinite loop.” But with a Turing machine, you can’t do that because in general you can’t do that. For all you know, it can keep discovering new configurations that you haven’t seen before. The contents on the tape can keep getting longer and longer. It can keep generating new configurations, combinations of what state it’s in and what’s on the tape that you have not already seen. If you’ve got a finite tape, then actually, the number of possible configurations that the machine can be in is finite. So if you have been watching a Turing machine and you’ve seen it write all possible contents onto the tape and go into all possible states that it could be in, then eventually it’s going to get to a point where it is back somewhere that you have seen it before. It’s either going to stop or it’s going to end up in a state that you’ve seen it be in before. In that case, you will know that it’s going to just keep repeating forever. Once it gets back into a state it’s already been in, it’s just going to do exactly what you’ve already seen it do. So yeah, a Turing machine with a finite tape, the halting problem is decidable for those, but not if the tape is infinite or semi-infinite. The tape doesn’t have to extend infinitely in both directions. It can have a beginning and extend infinitely off into the distance, and that’s still undecidable. DAVID:  If the tape is infinite, it can always, by definition, include everything you’ve seen so far plus the inverter at the end that makes the halting problem undecidable. TOM:  Right. JOSH:  Tom, what do you think that the impact of quantum computing has on this sort of decidability problem? TOM:  Firstly, I’m not qualified to answer that question. Secondly, my understanding based on what I’ve read from people who are qualified to answer that question like this guy called Scott Aaronson who write about this stuff a lot and he’s a mazing, so if you’re interested in that question you should go and read what Scott Aaronson’s written. He just wrote a book about it which is really fascinating. But it seems as though the consensus is that quantum computing does not fundamentally alter the situation. The quantum computing is all about complexity theory and the efficiency with which computations can be performed. If you’re talking about mainstream quantum computing, it’s just about being able to do complex stuff quicker, basically. It doesn’t fundamentally change what is computable. There are plenty of people who disagree with that and that’s why I’m a bit hesitant to even answer the question. There are a lot of people and a lot of extremely smart people, possibly including Roger Penrose who wrote a whole book about this, who feel that there is something ineffable about quantum mechanics that means that there is room for extra work to be done. There are things, and this is as far as I understand it, again I’m not an expert, but fundamentally this is the argument about the nature of the brain. Is it possible to just build a computer that’s made out of transistors that works like a brain? Some people would say no, it’s not possible because there is stuff going on in the brain that is to do with hand-wavy quantum mechanical stuff that you just can’t reproduce reliably on a deterministic, on a Turing machine basically. I don’t know how to decide that question. Obviously, if someone could present an existence proof by actually building a quantum computer that can decide the halting problem, that would be pretty impressive. We would know conclusively. But as far as I know, the jury is out on it and my layman’s intuition about it is that it probably doesn’t fundamentally alter the situation. But I know nothing. JAMES: **I want to take it back down a little and ask you an easy question so I can disagree with your answer. [Laughter]**JAMES:  Does this book affect my day to day Rails programming? TOM:  Well, that’s a good question. Probably not. Other than in the sense that I explained earlier, which is that it gives you something to hold on to. When you’re sitting there and you’re banging your head against the asset pipeline for the tenth time this week and you’re about to rage quit and you’re just like, “I don’t enjoy this anymore.” This is speaking for myself, but I have those days where I’m like, “This is something that I got into because it’s my passion.” I wanted to program computers from a young age because I found it exciting and fun and now it is not exciting and fun anymore because I hate the asset pipeline and I just want to throw my computer in a bin and storm out and just not work with computers anymore. For me, that’s really the practical value. As far as there is any practical value, it’s that I hope that it helps people to feel like they’re having fun and that they’re doing something cool when they write computer programs, because I still do feel like that. I’ve been writing computer programs for a long time. And when I have those days where I’m like, “Why am I even doing this?” I just stare out the window and think about how excellent and cool it all is and then that gives me a little kick of enthusiasm that allows me to continue configuring the asset pipeline. I don’t know. That’s not a convincing answer to your question. But certainly, I don’t think there’s anything in the book that is necessarily going to make your Rails code any better. There are a couple of practical things in it. I think it is worthwhile to know how regular expressions work. I think it’s probably worthwhile to know how parsers work. I think it’s worthwhile to be at least peripherally aware of type systems and abstract interpretation because those are cool ideas that have, maybe not for Ruby programmers, but if you are interested in programming languages that have static type systems it’s good to know about them. Even if you never touch one of them, it’s nice for that to be an informed decision rather than just being based on, “Well, type systems are just like a load of administrative overhead that I’m not interested in.” whereas if you can actually, if you’re dismissing them for the right reasons, then that’s absolutely fine. But if you’re just dismissing them as alien and weird, then that seems like a shame because static type systems are amazing and incredibly powerful and incredibly interesting. Maybe you should go and learn Haskell or at least maybe you should go and learn Java or Scala or something and at least expose yourself to these ideas. So I think it’s all a little bit, it’s a load of things that are in distant orbit around practical value. It’s just that none of them, every so often one of them comes in for a close approach like a comet, but none of them ever directly crash land on the planet or relevance. So I’m sorry about that. But I hope that the overall constellation of ideas is interesting to look at and aesthetically pleasing and helps people to want to keep doing cool stuff. JAMES:  That’s what I was hoping you would say, by the way. So here comes my disagreement. I think the interesting question is does this almost formal computer science creep into day to day programming of the type that we typically do? On one hand, I think people say, “Oh, I don’t ever see any of this in Rails programs,” which on some aspect is true, but on the other hand I think it’s, “Oh, you actually don’t see it because you don’t know what it is,” that if you were familiar with this, you would actually see this. So to give one concrete example which you circled around to is I’ve seen people billions of times write a regular expression where they nest a quantifier like a plus or a star inside of a quantifier like a plus or a star and then their application hangs. They always come to me and say, “How come this doesn’t work?” and I want to start that conversation with, “Okay, imagine a finite automaton,” but you can’t. So you just say, “Oh, you can’t nest quantifiers because it turns out that it’s too much work and it won’t get its right answer,” which isn’t true strictly. You can nest quantifiers under certain cases, but without this understanding, you don’t know where it applies to. Or your client comes to you and says, “We need to put in this program that figures out this and then we’ll do that in the background and then we’ll just wait on this webpage or whatever,” and if you’re familiar with these concepts, you can sometimes say, “Actually, it turns out you can’t know that.” That’s not right because it reduces to the halting problem or something not covered as directly in the book, algorithm complexity and how long it would take. We can know that, but unfortunately it would require more time than the heat death of the universe. There again, off the table. TOM:  Well that’s something that I very conveniently and very consciously completely avoided talking about. If someone else wants to write a whole other book like this about computational complexity theory, I would absolutely love to read that book. But I absolutely do not want to write it. Other than the very occasional hand-waving of, I always say in a deliberately sarcastically understated way of like, “This version of the computation might take slightly longer to run than the original one,” and usually what I mean by that is it’s going to take astronomically longer. If you encode even an extremely simple computation as a cyclic tag system, you’re going to have to run it until the heat death of the universe probably before you can even see your output. Just because these things are possible doesn’t mean that they’re efficient. But I was conscious that there was quite, as I said the whole book was really just a yak-shave to be able to talk about firstly, universality and simple systems and secondly, the halting problem basically. Those are the two. Rice’s theorem was what I really wanted to talk about. Everything that is there is just to support those two ideas and it felt like that was already more than I could handle explaining. So I just couldn’t really face the issue of talking about computational complexity. But that is an absolutely fascinating area that I don’t have a very good grasp of and I would really love it. I wish someone would sit down and properly explain it to me using Ruby code because that’s exactly what I need. So if this book can provoke someone who knows about that stuff to do what I have done but better and with something more difficult, that would be absolutely amazing because then I would finally understand it. All I’ve got to bring to the table is like, “Isn’t it cool that you can take a regular expression and then give it the notational semantics of that expression in terms of finite state machines?” Here is a procedure for walking over a regular expression and generating a little simple machine that will compute that. I think that’s quite cool. When I first read that, I was like, “Oh, it’s actually quite neat that you can get a regular expression and just by walking over it, turn it into a little machine that does the same thing as that regular expression. That’s fun.” Now, when I write regular expressions, I enjoy it slightly more than I used to because I can play a little game in my head of what does the finite state machine look like for this regular expression? That’s pretty basic stuff, but that’s the level that my mind is operating at right now. DAVID: **Also of practical value, from your book, you’ve specifically proved why you cannot parse html with regular expressions. [Laughter]**DAVID:  And then you give a footnote at the bottom that says, “But you can with Ruby’s regular expressions because they’re way more powerful than regular regular expressions.” CHUCK:  But it’s still not a good idea. TOM:  No. And I think I saw James enjoying on Twitter my link to the infamous Stack Overflow response to that question. JAMES: **I love that response. I give it to people all the time. Actually, there is one sidebar in this book that includes a regex to match balanced parentheses, which is one of my favorite things because everybody always tells me regular expressions can’t match balanced parentheses, which they can if you use Ruby’s regex engine obviously or Perl’s or anything like that. And a use of grep, which is an enumerable method I never see in the wild and the link to that Stack Overflow answer, that one stupid sidebar was cooler than a lot of the technical books I’ve read. [Laughter]**JOSH:  Hey, I actually learned some cool Ruby stuff reading this book. TOM:  Really? JOSH:  Yeah. JAMES:  Right, yes. JOSH:  I didn’t know about array cycle. TOM:  I saw James was complaining, not complaining, in the politest possible way, was saying that he doesn’t like Ruby chapters at the beginning of these books and I don’t really like those either. But I felt that I wanted to put that in there so that O’Reilly could market this book as for programmers rather than for Ruby programmers. But I’m very glad that you found some value in that. JOSH:  So the last thing I want to ask you about, because I know we’re running out of time here, is your choice of using Ruby for this book and whether that worked well for you and what was maybe the hardest thing about using Ruby or what made it awesome? TOM:  I think some people have been put off the book by that choice. I think a lot of people on reddit or whatever were not happy with the choice to use a language like Ruby to explain these ideas. But I picked Ruby for two reasons and one of them is just that I like it. I enjoy programming in Ruby. In fact, everything that’s in this book came out of me just playing, having sit down, thinking about stuff that I thought was interesting that I dimly remembered from learning it and then just building little interactive experiments and just little bits of fun. The things that didn’t work out and that weren’t fun didn’t go into the book. So I only put stuff in that I felt was sufficiently interesting and fun, that it was worth talking about. That was the first reason, is that I could not have written the book without having a language that I felt I enjoyed programming in enough to be able to just tinker with stuff and come up with executable explanations of things. But I discovered, in that process, I discovered that Ruby’s actually really good for explaining these things. It’s not ideal. There are things that are a bit more difficult than they should be and there are a couple of places in the book where I have to slightly bend over backwards to accommodate something or other for an uninteresting technical reason. There were a couple of places where I have to undefine a constant just so that I don’t have to do something worse and that’s a shame. But I found it incredibly useful to be able to explain things incrementally, basically because of open classes. I found that having open classes and being able to say, “Well, let’s make a little whatever.” In chapter two where I’m walking through the semantics of programming language, being able to firstly talk about syntax and define the classes for all of the different syntactic categories of the programming language and then being able to go back and re-open those classes and say, “Well now let’s define a reduce method on all of those classes,” and being able to explode explanations in that way by just being able to go back and define new methods or redefine existing methods on classes, I actually found that it felt like a decent fit. And it’s not a perfect fit, but it felt like it never got to the point where I thought I’m using Ruby for this just because I want to use Ruby for this and that’s actually, the cost is outweighing the benefits. I did start doing it with Ruby because that was the language I wanted to do it in, but I was definitely open to the idea of I might get halfway through this book and realize it would be much better to do it in JavaScript or to do it in a language like standardml for example, which has got much better support for functional programming and pattern matching and a load of features that I wish I had to be able to explain stuff, or doing it all in Lisp and then maybe the stuff about syntax I wouldn’t have to say so much because I could just represent everything with S-expressions. I was definitely on the fence about whether Ruby was the right thing. But then the more I got into it and the more of it I wrote, the more I felt like, in a way that I can’t quite put my finger on, it felt like Ruby was being strangely cooperative. The notion of a program as like a roiling pop of collaborating objects that are all just sending messages to each other and being able to go in and modify the method tables of those objects and put new implementations of methods into them whenever I wanted to meant that I could do this slightly weird thing where we’re walking through a chapter and it’s really just an annotated IRB session where I’m just, “Now if you paste this in on the console then all of your objects have this new method and you can actually call that method on those objects.” It felt like a natural way of explaining stuff and I was really happy with that because it helped me solidify some of the things that I really enjoy about Ruby. And actually, since writing the book I feel more enthusiastic about Ruby now. Again, it’s not just the glue that holds together your Rails application, it’s like a really fun and powerful and interesting programming language in its own right. It’s got idiosyncrasies and it’s got weird edges, but that’s what makes it cool and fun. It’s knowing about all of those edges and all of the weird bits buried in the core library and the standard library that that’s where I get my fun from. And also, I just hoped that the target audience of this book already know Ruby. I think that that again is an unspoken goal of the book, really. I could have written this whole book and done all of the code examples in Haskell and it probably would have been easier. But I don’t know if any of the people who I want to read it would have read it. JAMES: **That’s interesting. I feel like now I want to go, after having talked to you again, I want to go back and re-read the entire book. Because I feel like I caught lots of little things on the way through that now that I’ve talked to you reveal this deeper insight. Like in your description right there, you talked about how there were a couple of things that you hated that you had to do, like undefining a constant before you did something. And I actually have a note that says I still hate Ruby tutorial chapters. Remove const. Really? And that was actually, I was like, “Really? That’s the part we have to learn about Ruby in order to understand?” [Laughter]**TOM:  Well you and I had a very genial conversation on a gist about this right, where we were talking about the right way to define structs and pretty much everything that is in the book code-wise is a result of ridiculous over-refactored, I just obsessively moved the deck chairs around on all of the code in this book and tried a load of different ways doing it. I tried explaining things in different ways and I tried naming the classes differently. I made a decision as part of that Ruby tutorial chapter, I made the decision that I wasn’t even going to mention instance variables which was quite unusual for a Ruby tutorial. I also decided that I wanted to introduce singleton methods before I talked about classes. JAMES:  I loved that. That’s one of my notes, as well. TOM:  Oh, cool. So some of that stuff was a little bit unconventional, but it was the result of me, to a first approximation, just trying everything. I tried it every which way and then I just picked the way that felt like the least bad. And it felt like there was definitely a principle of conversation of pain at work where every time I got rid of one thing that was bugging me, something else cropped up and it was just a question of whether that thing that cropped up was better or worse than the thing I was trying to address in the first place. So unfortunately, that thing about remove const, I did that in order to avoid doing something which I felt would be worse. So that was something that is not great, but it is something that is totally orthogonal to all of the other stuff I was talking about. And I can, without guilt, I can just hand-wave it away and say, “Just don’t worry about this,” like this is not really relevant. It’s just some BS that we have to do in order to make progress and it’s not part of my explanation. It’s just something about Ruby that you don’t need to know about. That felt, although it doesn’t feel good to do that, it felt better than getting bogged down in stuff to do with inheritance and superclasses and singleton classes and stuff which I just really didn’t want to go there. JAMES:  You talked about the use of struct and we, like you said, debated that back and forth in a gist, and it’s interesting. Because now, also, we’re writing a book about the correct way to use Ruby line by line, pretty much. So we’re having those discussions again about struct and can you use it this way, can you use it that way? I don’t like that usage as much as I like the ones I’ve showed before, but as I read your book, I gained a deeper insight for how much you got out of that. So in the beginning, I thought you primarily did it to skip writing the initialize method, which is somewhat true. But then like you just said, you didn’t have to cover instance variables, because actually, you’re just using these struct accessors to get at the data that was already there. Also, you make use all over the book of the fact that struct gave you a meaningful equals method for being able to test if two objects are equal based on the contents of their attributes, which I thought was actually genius. The more I read it, the more I think that you’ve actually uncovered a failing in Ruby, that it doesn’t give us some way to define these simple data objects other than struct, that doesn’t come with all that baggage but does give us this data and this meaningful equals or something like that. So you won me over to your struct argument as I went through the book. TOM:  That’s excellent. I would like to use this podcast as a propaganda platform to reach people who care about Ruby to petition for the ability to define a struct that has zero fields. I found it deeply frustrating that you can’t do that. In fact, there’s a point in the book where I want one of those and I have to define it myself and have to implement equals myself. JAMES:  I noticed that, yes. TOM:  That made me very sad, because there is absolutely no reason why you shouldn’t be able to create one of those. All of the stuff in struct extends perfectly well to zero fields but the constructor, struct new errors out if you provide an empty list of fields. That is just a source of rage. So Ruby 2.1, let’s make it happen. DAVID:  Awesome. JAMES:  That’s so funny. I do have one other question now that I’m pretty sure I know the answer to. I’ve talked to you a bunch. But did you purposefully make it, as part of your crazy wall, was one of the goals teach some good programming habits along the way? Because I noticed several things I liked, like you use the functional aspect of keeping your primitives primarily immutable and you actually talk about that a little bit and the advantages it shows. I really feel like this was an awesome way to show how much you can get out of that when you’re doing things like state machines and stuff that change state every single time through. And they’re all immutable and you made that work. It wasn’t painful in these objects and it came out very natural and was cool. Another thing I noticed is, Josh probably loved this too, you used send a message correctly multiple times in the book. JOSH: **But not everywhere. Not everywhere. [Chuckles]**JAMES:  Oh, not everywhere? Uh oh. TOM:  Oh, man. JOSH:   I do have some notes on that. JAMES:  Well, you used it correctly several times, because I caught it a couple of times and noted that it was right. And then just teaching cool things like linked lists or infinite streams, old school infinite storage and stuff like that. I wondered if it was a goal to actually teach good programming as you went. TOM:  I think there are two distinct sides to that. One of them is that, the most important one is that I did not set out to make it a tutorial on how to write good programs. One of the things that was on my crazy wall was the code has to be in service of the explanation and not vice versa. I’m not going to go through any pain of talking about OO design or DRY or any of that stuff just for the sake of it. So everything had to be relevant. For example, there is a whole, I’m sure that all of you when you were reading this got to places where you’re like, “I wish he would just declare a mixin or I wish he would just inherit from the superclass,” or whatever your preferred method of object composition Is. And I just decided I didn’t want to get into that. I didn’t want to have a sidebar that was like, “Oh, by the way what we’re doing here is that we’re trying to extract this concern into a small self-contained object so that we’re doing proper OO programming.” I was very keen to not do that. So I had to grit my teeth in several places because I knew that I was writing “bad” code. But I also had to remind myself that that didn’t matter. So that was the main thing. However, obviously, every time there was an opportunity for me to get out my functional programming hammer and hit people over the head with it, I never missed that opportunity. So yeah, I was careful to try and, again without necessarily calling it out, to just make the code as good as I could without it being an impediment to understanding. That thing you said about immutability, it’s doubly useful. Because firstly, it gives me an opportunity to show you, you can have stuff be immutable and you can write these pure functions that just return a new object rather than a modified version of the original object and everything can still be fairly clean and understandable and hopefully more understandable. That’s why I did it that way. It was not because I enjoy hitting people with the functional programming hammer, but because I wanted them to see. I wanted them to be able to understand the code I was writing. That is just how it makes sense to me, is to have these immutable value objects. Secondly, because it was actually necessary to make the code work. Where I do that stuff, the way that I do the non-deterministic finite state machines and the non-deterministic push down automata, those only work because effectively what you’re doing is you’ve got these objects that represent the state of the machines and then you allow more than one path to be explored. If I’d made everything mutable, you can’t explore more than one path because as soon as you start exploring one execution path, you’ve destroyed the history. You’ve mutated your finite automaton. So you can’t then go back and say what if that machine had gone the other way? So it was really just born out of necessity, actually, to actually do the stuff I wanted to do and make it clear. I had no choice but to program in that style. Of course, that is why I think that style of programming is good. But that’s not the reason. Just because I think it’s good was not enough reason to put it in the book. It was only because it was pursuant to firstly, making the code work and secondly, making the code clear. JAMES:  I love that answer. And to solve it in an object-oriented way, you have to do something like introduce some kind of stack where you’re pushing your state onto that stack so that you can, when you backtrack, then you can yank your state back off that stack or something. TOM:  Right. JAMES:  Awesome. DAVID:  So I have one last question for you, Tom. TOM:  Okay. DAVID:  So this one might take you out of your comfort zone because I want to talk less about computational theory and more about your opinion. As you answered Josh’s question about why Ruby, you kept using the F work. You kept saying fun. And I don’t want to give away the end of the book, spoilers the butler did it, but you get to the end of the book and you say something that makes me feel very ambivalent. You basically say all programming languages can ultimately be boiled down to a Turing machine. And that makes me feel happy and awesome and that everything’s great and equivalent and universal. Then you say, and every computational mechanism we’ve ever devised ultimately scales up into a Turing machine, into Turing equivalence. And I suddenly got very, very depressed. I realized that what was happening is in one hand, I had Turing equivalence, on the other hand I had the Turing tar pit. The Turing tar pit is where everything is possible but nothing of interest is easy. So I love Ruby and I hate PHP with a legendary fury. And I’ve talked to people who love Haskell and its provability and immutability and all this stuff and they hate Ruby and its statefulness with the same kind of hate that I have for PHP. And now I’m realizing that these are all Turing machines. These are all Turing equivalent. So the tradeoff is not about power or about Turing equivalence. So you talked earlier about fun, so I want to ask you. What is your opinion, what are the things that you select programming languages for? What makes a good language for you? TOM:  Well, in general, it obviously depends on what it is I’m trying to do and that’s the really boring answer. But let’s pick something that’s fitting for purpose. But setting aside all of that and in the abstract world of me sitting down on a Sunday and I want to write a program and what programming language do I choose? It has to be about, yeah, basically that sense of fun. I think that’s what I get excited about. Ruby is a really excellent sweet spot for me because it’s an improvement over the first programming language I ever learned which was BBC BASIC. In the UK, in the 1980’s, we have this national program where all of the schools in the country got these microcomputers so the kids could learn to program on them. When you turned on the BBC Micro, you would just get a prompt and you could start typing BASIC programs. I got a huge visceral thrill out of that as a kid. The ability to just type 10 print “Hello, Tom” 20 GOTO 10, gave me massive kick. So I think Ruby has some of that feel to it. It’s not nowhere near as simple as BBC BASIC, but it’s got this wonderful accessibility and it has that thing that I can’t describe any better than like that Smalltalk feel. We haven’t quite gone to the level of the actor model. We’re not quite writing programs in Erlang. But we are getting some of the benefits of thinking of our program as a load of interacting objects, a load of little entities that are sending these little messages to each other and everything’s very loosely coupled and everything’s runtime dynamic dispatch. It’s all very easy-going and very relaxed. I just find that very liberating and very fun. As the research that I did as a graduate student was not about this at all, it was about static type systems and I was very interested in what’s possible with type systems. I find those also extremely elegant and beautiful and useful and interesting and all of that stuff. But for whatever reason, I don’t find myself naturally reaching for strongly typed or statically typed, I should say, programming languages. And I do really like Haskell. I think it’s an amazing programming language. I find it fascinating and I do Haskell for fun sometimes. But I think it’s the fact that Ruby has that kind of untyped or dynamically typed, I keep getting my words wrong, but you know what I mean. It allows you to just have this sloshing pool of objects and anything could happen and its’ very easy and fun and relaxed and it just has a kind of feel to it that a lot of other programming languages don’t manage to have. That’s been nicely amplified by Rails, I think. There’s another three-hour podcast in what’s wrong with Rails, but Rails has really nicely leveraged that property of Ruby. It lets you feel as though the machine is working with you and you’re just getting to say the things you want to say in the way you want to say them and everything is just somehow working. And obviously, the problem with Rails is you don’t really know why it’s working. But it has that kind of, when you’re sitting down and you’re doing Ruby, it puts you into a state of mind that I think means that you can have fun more easily and that you are, for better or worse, you are less constrained by the computer’s expectations of you. It’s like I was saying about the tower of abstraction. It’s giving you something that’s very close to, in a sort of Larry Wall sense, it’s very close to what you wanted to write and what you were already thinking. I think that humans don’t naturally think in a statically typed way. I think we live in a world where objects, by which I mean literal objects, do have a dynamic type. There are actual ducks, ducks actually do quack. I think that Ruby has that kind of humanist quality to it that some of the other languages that are more into punishment, although there are loads and loads of benefits to being punished by your programming language, I just think it attracts a different kind of person and it puts you into a different mindset when you’re writing your program. Even now, I feel very strongly that programming is a mathematical activity. And I tried to explain this a little bit in the book, that when you’re writing a program, firstly you’re just writing down a gigantic number, so writing down a gigantic number is an inherently mathematical activity anyway, but all of the stuff that happens in terms of the evaluation of your program can be understood mathematically and that doesn’t have to be in a formal mathematical way but in the other sense of thinking about things in terms of abstractions which is what mathematics is, really. That’s what programming is. So you should be able to think mathematically about your programs. But for me, it doesn’t necessarily follow that I want to spend all of my time working in languages that make me work like a mathematician all of the time. When you work in languages that have very advanced type systems, you do have to think much more formally when you’re writing programs. I think it’s nice that Ruby is a bit more chilled out than that because that’s the mode I like to be in when I’m trying to be creative. I think being able to be in that open mode and think creative thoughts is super important to me, because otherwise I just can’t get anything done. Ruby lets me be in that open mode for more of the time and spend less of the time in the closed mode of just frowning at my computer and wanting to rage quit. So that’s why I like it. DAVID: **That’s awesome. You used that phrase sloshing pool of objects and you used it as a feature of a thing that you love about Ruby. But you also said fit for purpose. I like that because it made me realize that I don’t know a single defense contractor who would not be terrified by that phrase, sloshing pool of objects. [Laughter]**DAVID:  They want something formal and provable. So give us something more fit for purpose. I like that. Thank you. JAMES:  I think your enthusiasm for programming in the book and on this call is just super infectious and I hope it spreads through the entire community because that is definitely how I feel every day. I wish Katrina was here because she explains some of these things better. She told me one time, it’s like, “What if you’re working on a web app for car ads. Isn’t that lame?” and she’s all, “Yeah, of course car ads are lame, but it’s the code. The code’s the interesting thing.” It’s why is this variable here, does this variable need to be here? Isn’t there a way that we could make this variable go away? Can’t we use method dispatch and just bypass all of this work? Or whatever, and it’s clear that you share that enthusiasm of how it all works and I think it’s just super cool. DAVID: **Yeah. You may not know anything about computers, but you’re clearly passionate about them. [Laughter]**DAVID:  And that’s what we love about you. TOM:  That’s what it’s going to say on my gravestone, I think. That’s a good way to go. CHUCK:  Alright. Well it sounds like we wound down. Anything else before we wrap up and do picks? JOSH: **No, no. Let’s do picks. [Laughter]**JOSH:  Actually, I have one last thing for Tom and that’s Tom, where are you speaking in the future? Do you have any speaking things lined up? JAMES: **That was a slow pitch over home plate. [Laughter]**TOM: **That is a very good question, Josh. I will be speaking at the Golden Gate Ruby Conference in San Francisco and I’ll be speaking about The Halting Problem. So if you’re interested in the halting problem, come to that conference. [Laughter]**JOSH:  Oh, okay. CHUCK: **I love the way he said it as, oh, a sales pitch. [Laughter]TOM:  Look, that was totally natural. JAMES:  Yeah, it seemed very natural. JOSH:  We did not discuss that. Unfortunately, GoGaRuCo is already sold out. Are there any other opportunities people would have to see you speak? TOM:  No, that’s it right now. I’ve put in a proposal for RubyConf, but who knows what’s going to happen with that. Maybe in November in Miami but fingers crossed. JAMES:  If they do not take your proposal for RubyConf, we will riot. CHUCK: [Chuckles] All six of us.**TOM:  Awesome. JAMES:  Exactly. CHUCK:  Alright. JOSH:  Okay, so picks. CHUCK:  Josh, why don’t you start us off with picks? JOSH: **Yeah, because apparently I’m eager. [Laughter]**CHUCK: **That’s right. [Laughter]**JOSH:  So I have a couple of picks that are relevant to the topic. As Tom mentioned, in one of his impossible programs, or was that universality, where you’re talking about the game of life. You talked about how it was Turing complete. I saw these videos a while ago and I dug them up and there are some pretty cool videos showing the execution of Conway’s Game of Life doing a Turing machine. It’s just astounding to watch and see how it does things like pushing values on the stack and it’s totally cool to watch. So that’s fun to check out. There’s also, you can search around and find all these other things that people have built Turing machines in like Minecraft. People have videos of that. I don’t have any links to that. But it’s worth doing a little hunting around. Then the other thing is Rule 110, a cellular automaton system, which is astounding, but it also occurs in nature. So there’s couple on mollusks, sea snails of a sort, their shells are essentially the Rule 110 cellular automaton. They have exactly the same thing going on where the cells that create pigments are influenced by the amount of pigment in their neighbors and you can see exactly the same kind of pattern evolving on their shell as the shell grows. I just linked to a Wikipedia page that shows that. JAMES: **I’m getting Rule 110 on my tattoo that I’m getting in two weeks. So when it was in the book, that just totally validated my choice. [Laughter]**JOSH:  And then I just have a silly one, which is a link to a description of an Easter egg in Google Maps where apparently if you wandered down the right street in London, there’s a picture of a police call box on the sidewalk and if you navigate your map into the call box you find yourself in the control room of the TARDIS. JAMES:   Awesome. DAVID:  Very cool. JOSH:  Okay, so that’s it for me this week. CHUCK:  Alright. James, what are your picks? JAMES: **A friend of mine that I used to work with made me aware of this tech blog recently that I hadn’t run across before called Building Wanelo and I was just poking around on it and I found some super cool articles that I really enjoyed reading. There’s one on how to do events on Rails applications. It uses this little gem, but the gem’s actually very small and simple and just the idea of how you extract code out of a Rails controller. It’s the kind of thing we talk about all the time on this show and shown in a super clear way here and I like how the gem makes that even more accessible. The gem’s called Ventable by the way, I think. So check out that article. Some cool other ones that I read on this blog, they had a neat map/reduce article doing the map and reduce steps using a [planal] units utility, so cat, aux, sort, [inaudible] that kind of stuff. Really interesting reading there. Then there’s this other article I like on “vertical sharding” and I’m not sure I agree with the language used there to describe vertical sharding and what that is. But the process is really neat in that how they’re busting up this table and they gave you these series of steps for doing it, like replacing any joins with these helper methods and then we could adjust these helper methods so they lived in different databases and blah, blah, blah. It’s really interesting reading. So it’s just a cool blog that like I said, a friend of mine made me aware of and I had some fun poking around on. I hope other people do too. Those are my picks.**CHUCK:  Awesome. David, what are your picks? DAVID:  I just have one. This is for everybody who listens to this show who loves WWE wrestling and is also a grammar pedant. CM Punk is a wrestler, apparently. I’ve been out of following wrestling for a long time. He does a YouTube show called Grammar Slam and I love what I’ve seen so far because the slam is sometimes literal. What I will link to is his episode where he talks for two and a half minutes about literally versus figuratively because we had that slip earlier in the show. I’ll link to that in the show notes and from there you can get to any of CM Punk’s Grammar Slam’s other episodes. I thought I had a huge list of other picks for the show but I think CM Punk is good enough for today. CHUCK:  Awesome. Alright, I’ve got two picks. The first one is, I made the joke on the Freelancer show that there’s still gray matter on the wall and I’m not sure if it’s because I hit my head that hard on the wall or if it’s from when my head exploded trying to use QuickBooks. But anyway, it just didn’t work out so I wound up trying LessAccounting.com. And wow. It’s a whole lot easier to use, makes a ton more sense. It’s something that I can actually do my books in. So if you’re the solo freelancer type person and you need some kind of bookkeeping software, that’s one that I highly recommend. The other one, I’ve been picking up iPhone programming here and there. And I’ve been going to The Big Nerd Ranch Guide to iOS Programming. They have a new version or a new edition coming out in January I believe. But the current edition is pretty good and so far it’s worked well with the version of Xcode that I have. So if you’re interested in that, then go check that out as well. Tom, what are your picks? TOM:  I have three picks which are all tenuously related to learning and teaching. The first one is a book called Learn to Program by Chris Pine. Recently, a few months ago, it has had a second edition. It’s a Pragmatic Programmers book. It is for total beginners, but I think it’s really good. If you even want to teach someone how to program with Ruby, I think this is an excellent book to do it with. The one feature I wanted to call it out for is that it has lots of exercises through and it has the answers at the back of the book, but the solutions that it gives are in two flavors. He gives a solution which is how you could advance at this exercise using what you know so far, ‘what I’ve taught you in the book’, but then he has ‘here is how I would do it’. So for every one of these exercises, you can see not only how you should have done it based on what you’ve been taught, but also how a super powerful idiomatic Ruby programmer would solve it. I think that’s an excellent idea so I just wanted to call that out. My second pick is a gem called showterm, which is effectively a screencast recorder for the terminal everyone’s been talking about the last couple of days. But I think if you haven’t seen this and you’re interested in explaining stuff on the internet, it seems like a super powerful way of doing that. So it’ll just record everything you do in your terminal and upload it to a URL and it’s all just done with JavaScript. It’s effectively replay your terminal session using just JavaScript in the browser and there’s a scrubber and you can change the speed and stuff. If you’re writing an interactive tutorial about how to do something, think having these embedded explanations of things that actually show you what’s going on in the terminal. It’s super useful. So that’s worth checking out. My third pick is self-promotional which is that the next thing I’m working on is a little eBook and screencast thing trying to explain how web applications work. It’s targeted at people who’ve maybe learned Rails and know how to make associations between Rails models but don’t really know what is actually going on. I’m still working on this. But it’s effectively going to be a bottom up explanation of how you can write a web application just using pure Ruby from opening TCP sockets through to parsing the HTTP requests through to making a request to the database and then sending a response and then explaining the structure of frameworks like Rails and Sinatra in terms of all of that code that you’ve written and showing what they do for you and how they do it and stuff like that. It’s really aimed at intermediate people who want to get a better understanding of how web applications actually fit together and work. That’s at RubyWebApp.com for anyone who’s interested. Those are my picks. CHUCK:  Awesome. JAMES:  That is so cool. DAVID:  Awesome. CHUCK: ** Alright. Well we’ve gone way over. So I’m just going to wrap this up. Thanks for coming Tom and we’ll catch you all next week.