Switch Statement

078: Gödel, Escher, Bach - Ch. 13 - Just Put it in an Earthenware Pot

• Jon Bedard

Share episode
Matt:

Hello everyone And welcome to the switch statement podcast It's a podcast for investigations into miscellaneous tech topics Hey, John. How are you doing?

jon_pt1_raw:

Hey Matt, how are you?

Matt:

I am doing okay. Doing okay. Just, uh, I don't know, in the middle of my law school semester. Uh, so,

jon_pt1_raw:

How's that going? You learning about all of our good, good laws?

Matt:

um, I don't know if I would call them good, but, uh, I'm, I'm learning about them, but, uh, but yeah, but we're not, uh, we're not talking about laws. We're talking about something.

jon_pt1_raw:

Bloop.

Matt:

heady. Yeah. Bloop, yeah, I mean, the law makes about as much sense as bloop, floop, and gloop, as far as I'm concerned. There's a lot of, uh, you know, really, uh, out there terminology like res ipsa loquitur, like what is that, uh, but

jon_pt1_raw:

Wait, is that a law thing?

Matt:

that's a law

jon_pt1_raw:

Was that a language or was that

Matt:

That's Latin, yeah, it means the thing speaks for itself, but,

jon_pt1_raw:

oh, wait, wait, say it again. I kind of

Matt:

res ipsa loquitur.

jon_pt1_raw:

Res ipsa loquitur.

Matt:

The idea is like, in certain circumstances, like, let's say you're walking down the street and like, you just pass out. You don't know what happened. You didn't see anything happen. But then other people like saw that people were lifting barrels like above your head. And then, like, the court is like, well, we don't have direct information about someone being like negligently moving the barrels. But we know that the, this guy was hit by a barrel, and it wouldn't have happened unless they were negligently moving the barrels.

jon_pt1_raw:

Is this the scenario they use to teach you this concept? Cause that is the most contrived scenario.

Matt:

This actually happened. Bern v. Bodal. Look it up. This is the, uh, You know, this is the seminal case on Rez Ipsilaquiter, where, uh, You know, B and that's B Y. R N E V, BODL, B O A D L E. Uh, yeah, some guy got hit by someone moving, like, wheat barrels out of a second story, like, warehouse. Uh,

jon_pt1_raw:

Law Corner, like section of the podcast

Matt:

know, yeah,

jon_pt1_raw:

play some weird music and then you can discuss like a weird court case.

Matt:

but anyway, that was not, uh, my goal was just to say that there's a bunch of silly words in, uh in law. Um, not much sillier than bloop, floop, and gloop. But, um, but that is, that's what we're talking about. We're blooping, we're flooping.

jon_pt1_raw:

Are we glooping?

Matt:

Are we glooping?

jon_pt1_raw:

We'll find out.

Matt:

in to find out.

jon_pt1_raw:

Did you read the dialogue in this one?

Matt:

oh my gosh, the dialogue was so long that I had to just stop reading the dialogue. Uh,

jon_pt1_raw:

So you were, you were smart. Uh, I did read it though, because they were talking about the Goldberg variations, which is one of my favorite Bach pieces, super famous, uh, Bach. Well, I don't know if I should call it like a piece, cause it's kind of a set of pieces. Uh, but there's a really, really famous recording by Glenn Gould where he plays the Goldberg variations and it's like Hannibal Lecter's theme song and all that. Um, But anyway, so this, this sort of made me want to read the, the whole dialogue, but, uh, I don't know if I would recommend reading this whole

Matt:

I read, I read that part originally and yeah, so they're, they start to get into all these different math problems like the Goldbach conjecture, uh, and I mean, eventually the, I think the point of it is to introduce the question of, do you always know how long it's going to take to evaluate a certain, you know, a certain mathematical goal? property of of numbers.

jon_pt1_raw:

yeah, exactly. They introduced the tortoise numbers and the Achilles numbers. And yeah, one of them is, well, anyway, we'll, we'll discuss this later, but one of them is like computable and always ends and the other one could go on forever and never really finish.

Matt:

There was this very brief aside where apparently Bach was paid a hundred Louis d'or, which is like the currency, I guess at the time. And I was curious how much that was. And that would have been worth 62, 000, uh, in today's, I mean, the gold, the gold value of it would be

jon_pt1_raw:

And this was for the Goldberg Variations.

Matt:

Yeah, for the Goldberg Variations. Which is also always funny to me, I was like, why is this called the Goldberg Variations? I never knew. And I guess it was after the guy who played them, even though he didn't write them.

jon_pt1_raw:

Yeah, that's kind of a I mean, if you Like, I have an edition of the Goldberg Variations, and one of the first paragraphs in the foreword is like Why the hell is this called the Goldberg Variations? Like, the music was written for a duke, or a count, or whatever. And it was written by Bach. But yeah, like, there was just some prince or something that was playing it, and for some reason it got named after him.

Matt:

that's so funny. Um, But, but yeah, so back to the, back to the core part, well, let's, we'll start at kind of the, the start and, and I guess it's always useful to kind of refresh our context here, which is that we keep on coming back to this idea of high, high fidelity number systems and low fidelity number systems, where it's like, if you have this crappy number system, which has all these flaws, You're not going to be able to do this self referential trick where you, you know, you, as, as he puts it, you play a record that is designed to break itself, like a refrigerator. It's not going to do a very good job of playing a record player. And, and it just, on its face, it's not a perfect record player because it's not a record player at all. But then once you start to get into the record player territory, you start opening yourself up to being able to play these self breaking records, which play a sound which is tuned to destroy the record player. And this is this metaphor for these numerical systems. Uh, and, and, you know, this is what these chapters start to, start to try to do is like, get at a specific example of creating one of these self breaking record, records, basically.

jon_pt1_raw:

Right. Right. Yeah, and so he gets into Bloop, which is sort of this first I mean, it's essentially a programming language. Uh, but it lacks a few key features of like an ordinary programming language. Uh, and one of the main ones is in Bloop, you can only have a for loop that has a well defined termination. So if you're, you know, if you're looping through something, it has to end after, you know, 10 iterations where that number is like defined in the code itself. Right.

Matt:

for, for it to be, say, a function of the, let's say, let's say you're computing n squared and you want to just iterate n times. That's okay. You know, you can, if you pass, if you, if you want to compute 10 squared, you don't necessarily need to know when you're writing it, that you want to loop 10 times, but what you can't do is do something. And this is this very subtle distinction here, which I think it's, it's almost hard to come up with an example of something that like a simple example of something where you would need an arbitrary number of, of steps, or like, you don't know at the outset, even when you know, What number you're working with how many steps you're going to going to need to take

jon_pt1_raw:

exactly. Yeah. And actually they use an example that I really like there was, there was a number file video about this a while back, which is that sequence where you take a number and, uh, man, I can't remember the exact steps. I think it's, if the number is odd, you like multiply it by three and add one. And then if it's even you divide by two, is that what it is? Okay, nice. Uh, that was purely from memory, but anyway, that sequence is amazing. Like if you do different numbers with that sequence, you'll find that oftentimes it will resolve in one. Like if you keep doing that sequence over and over and over again, it will eventually become one and that those numbers are called wondrous numbers,

Matt:

ah

jon_pt1_raw:

which I guess is a play on one and you know, whatever. But then other times you do that sequence and it just goes on and on and on in kind of an insane Like it just feels so arbitrary because you'll do the sequence with like seven and it will have like a whatever eight loops And then it ends in one but then you do it with eight and it goes on for like 250 million loops or something And it's just this super fascinating, you know set of operations that forms these really Sort of counterintuitive sequences, but the idea is when you start with a number, you have no idea how many times it's going to iterate like In fact, a lot of people think it could could be infinite

Matt:

Right certain numbers Well, right, and this is the thing. I guess the conjecture is that every number will eventually converge to one,

jon_pt1_raw:

Well, it will either converge to one or it will loop it will kind of ping pong back and forth between Because that happens sometimes where it ends on some sort of like and it's not necessarily two numbers It could be a sequence of numbers that just repeats and repeats

Matt:

Right, right, right, right. Because I guess you have that with one, because you can do that with one, because it's odd, and you can multiply it by three and add one, and you get four, and then you just go back to one. Like, then it's four, two, one.

jon_pt1_raw:

Right,

Matt:

So that's a

jon_pt1_raw:

exactly. Yeah, that's a loop right there,

Matt:

So, So yeah, there's a question of, they have these suggested exercise and immediately you get into this question of what can you do with a programming language where you're unable to have these arbitrarily defined long, you know, sequences. Uh, and it's, it's so funny. I mean, one of the first ones he talks about is Fibonacci, which. It's so funny that Fibonacci is the canonical example of, of recursion because it is so easy to come up with a non recursive version of it. Like you don't need to, uh, you don't need to, like, you can do this with Bloop, right? Like, uh, you don't,

jon_pt1_raw:

totally. Yeah, yeah, yeah. Because you just need to, well, there's obviously a trillion ways to do it, but one way to calculate Fibonacci is to just. you know, have a for loop from one to the nth number that you're calculating, and then just keep track of the like curr and previous. And it's, it's like you're saying, it's fairly trivial. Um, although it is nice, I think the Fibonacci function is one of the first examples where recursion feels really elegant. Um, and so from that angle, it's cool, but very easy to define without recursion.

Matt:

Um, but so I guess it probably is worth just just describing what the Fibonacci function is in case like people are not familiar. So it is just the sequence of numbers where you literally I mean, it's defined. The first two elements are defined as one and one, and then every subsequent element is defined as the prior two elements added together. So then to get the third element, or I guess the third element. If you're starting at, if the first one is zeroth, this is like the second, anyway, um, I'll just use one index. So if the third, the third element is one plus one, the fourth element is, uh, one plus two. Cause then, cause we just generated two. And then now the, the fourth is, is five because you had two plus three. So, um, so that's the Fibonacci sequence. And, and you say that it's recursively defined because it is a function. Um, you know, you have to look at the earlier generated numbers in order to produce the subsequent ones. So it's not, you know, obviously another simple function, it's just n squared. You don't need to look at, there's no history that you need to care about, which makes this function kind of like the most trivial example of a function where you kind of need to care what the past values of it were.

jon_pt1_raw:

Yeah. Yeah. Nice. Uh, and one, one sort of definition I want to throw out just cause I feel like this is gonna come up is Bloop is an example of primitively recursive where, and, and basically my understanding of primitive recursive is that all the four loops have fixed bounds. So it's just any, any set of, you know, sort of logical statements that you can string together where nothing is unbounded. That's, that's what's referred to as a primitively recursive language

Matt:

And the other super important thing that you cannot do in Bloop is there's no self referential procedures. You're not allowed to, because, because if you were able to call a procedure, if a procedure were allowed to call itself, that then allows you to, uh, to create these unbounded, this unbounded iteration. So, um,

jon_pt1_raw:

Yeah. You can only call procedures that are like defined above you basically.

Matt:

you, yeah. And that's kind of how they get around this. And I don't think he ever explicitly I mean, I don't think he wanted to say that because it might confuse the, you know, the point he's trying to make, but uh, but yeah, so, and then he says that Bloop functions anything that's expressible in Bloop is primitively recursive, which I feel like for anyone who has learned at least a little bit of programming, that term is kind of confusing.

jon_pt1_raw:

Yes. Yeah, no, I took me, I had to read the wiki page on this a couple of times.

Matt:

Oh, actually. Yeah. So I have not, I didn't look around, look outside of that. It did there, was there a more precise definition that they gave for primitive recursion?

jon_pt1_raw:

Primitive, like the definition that I have is it's computable, like it's, it's a system that's able to define computable things. And I guess computable meaning that, uh, well, and this is, this is where we get into what does computable even mean? Uh, but basically like being able to combine numbers using like a well defined set of operations.

Matt:

Hmm.

jon_pt1_raw:

Where everything is a for loop with fixed bounds. That's the, that's the definition I have. Or I, I guess I tried to find kind of like a one sentence definition, so there might be more nuance that, that's lacking.

Matt:

Right. And then I guess in terms of the effect of those constraints. For any inputs, the, for any particular input, the number of steps that a function will do is always bounded. And that's what bloop means. I don't think we describe that. It just means like a bounded loop.

jon_pt1_raw:

Yes. Exactly.

Matt:

Um, so I guess that's, I guess that's kind of the thing. And one question I had was, Is primitive recursion the same thing as tail recursion? Like it. Is anything that's tail recursive also primitively recursive?

jon_pt1_raw:

That's a good question, because I feel like with tail recursive, you can definitely create, you know, these sort of non halting Um, because I guess the minute where you can call a function within itself, you immediately introduce like, uh, just literally a function that immediately calls itself. And that's like an infinite construct. So that's a good question. I'm not sure. My initial take would be like, no, that's not allowed, but

Matt:

Right. That, like, and this is what always confused me and, and tail recursion, I guess. And I've always found, I'm already, I'm still grappling with it. I feel like

jon_pt1_raw:

yeah, Oh, me too. Yeah.

Matt:

Um, so, I It's probably just a mistake to try to describe it, but I guess the idea is that, you know, recursion is when, like we were talking about, it's a procedure that is calling itself. But if you do that at the very end of your function, that allows you to have this kind of like trivial, trivially change it into something that is

jon_pt1_raw:

Exactly. Yeah. There's a well known sort of compiler optimization that when you're doing tail recursion, you don't have to push a new stack frame. You can kind of like reuse locals and things.

Matt:

And I guess, I guess that was what was making me feel like. If this is kind of a, yes, the core act of defining the recursive function does allow you to do, make these unbounded things. But I guess I was thinking that if it was tail, tail recursive, that that was kind of falling back into the simpler mode, but they may, they may actually be just two, two separate constructs.

jon_pt1_raw:

Yeah, it is interesting because I think you're absolutely right. The tail recursion is like a much, much simplified. Like case of recur, of more general recursion.

Matt:

And that's, what's so confusing about the fact that, cause he's using, he's using primitive recursion in this example to refer to bloop. But then as programmers were like, there's no recursion here. Like, what are you talking about? You know, uh, I think that's the most confusing thing because at least when I think recursion, I think, I think a function that's calling itself. So

jon_pt1_raw:

Oh yeah. So it's weird. I, I completely agree. And this was a massive misunderstanding that I had, like, until I was almost done with the chapter and I like went back and kind of reread, uh, but yeah, it's like a bloop can never call it's like if you're in a function in bloop. You can never, like, re enter into that function from within that call.

Matt:

Exactly.

jon_pt1_raw:

Which is, which is a massive, you know, no modern programming language has that restriction. And he sort of mentions this later. But it's like you just lose a tremendous amount of expressive power when you have that limitation.

Matt:

Right.

jon_pt1_raw:

Um, I just wanted to throw out, just cause I sometimes like the languages Douglas Hofstadter uses and like his little phrases, he, he mentions how bloop is, can be thought of as like a chain of functions. And this goes back to that thing where like, you know, if you're calling a function, it has to have already been defined. So you can kind of think of it as like a previous link in like a long chain. He says it's like a meat grinder.

Matt:

Oh,

jon_pt1_raw:

you kind of put meat in the beginning and it just kind of goes through this chain and gets all ground up. I just thought that was such a bizarre way of describing it. I kind of liked it.

Matt:

Yeah. Um, This was, this was very interesting because at one point he defines these primordial steps for, and these are, you know, for kind of diving into a little bit more of the specifics of Bloop. Uh, He says that the base operations are you can add any two natural numbers, you can multiply any two natural numbers, you can determine if two numbers are equal, and then you can determine whether or not two numbers are smaller or larger. And I immediately just thought about chip lord. Basically, this is a game that john john worked on a little while back, but you know, the idea is you have these like absolutely. Truly basic functions at the bottom and then you, but I'll let you describe it, uh,

jon_pt1_raw:

Yeah, no, I love that you randomly thought about chip Lord, but yeah. Like, so in chip Lord, the premise is that you're creating chips and you start with these extremely

Matt:

like, um, tortilla chips or potato chips or

jon_pt1_raw:

Computer chips. I wish it was, man, if it was tortilla chips, I think that could be the, that could be the hook. But in any case, you're creating, you know, silicon sort of computer chips. And you start with this set of very contrived, like primitive operations. You know, like, one of the operations is called repeat, where, like, a number goes in and, like, two duplicates of that number come out. So it's not, it's, you know, there are some basic math operations, like, I think plus was one of them. But it's also, like, conspicuously lacking, like, very basic math operations, like there's no multiplication. Uh, so the objective in Chip Lord is to build these chips and sort of create some of those fundamental operations. Like one of the first missions is to create a multiply chip. And then later in the game you have to like use your own chips to kind of combine them. Uh, and so yeah, you'll define like a multiply and later use it to like launch a spaceship or whatever. Yeah.

Matt:

of the Like you could make a bad chip. You have like excessive, you have all this excessive piping and like you have too many operations and so like your chip's just bad. Uh,

jon_pt1_raw:

Yeah, no, it was very easy to make a bad chip. It was also very easy to make a chip Like, in Chiplord, sort of, numbers would, like, physically move along the wires. And it was very easy to make a chip where, like, a wire would just get filled up with numbers. And it would, break, basically, no new numbers could come in because the wires were clogged, and so it had these, had these, like, very interesting sort of failure cases, that like, have no analog in actual programming,

Matt:

Yeah, yeah, yeah. I think that, I think that's probably a good thing. Um,

jon_pt1_raw:

it was cool.

Matt:

Uh, did you have, uh, did you have any other, uh, points for this?

jon_pt1_raw:

Yeah, one, one last thing I did want to mention is just to sort of define what the Goldbach conjecture is, because I think there's an important reason that he kept mentioning the Goldbach conjecture. I mean, for one, it's Goldbach, Goldberg, sort of this interesting play on words, but the Goldbach conjecture is that every even natural number greater than two is the sum of two prime numbers. And it's called a conjecture because it's still not solved. Goldbach introduced this conjecture, you know, a trillion years ago. And mathematicians are still wrestling with it, trying to come up with math that can actually capture it. But one very notable thing about the Goldbach conjecture is that it is primitively recursive. It always has an upper bound. on the number of checks that you have to perform in order to tell if something is, uh, or, you know, satisfies the Goldbach conjecture. Because you never have to exceed the inputs. Like if you're trying to check if some number is the sum of two primes, then you never have to check beyond that number.

Matt:

Right, right.

jon_pt1_raw:

so anyway, it's an example of primitive recursion, recursive.

Matt:

right, but then there's the meta problem of proving the Goldbach conjecture, right? And that's, you know, well, I guess that is just You just can't do that, uh, mechanically. And I guess this is a point that he makes a while back where it's like, you can just keep on checking but that's never gonna prove it.

jon_pt1_raw:

Right, and we have, I mean, I think we've, you know, so we've checked numbers up to like, I don't know, 10, 000 digits or 10 trillion digits. And it seems like the Goldbach conjecture is true, but there's, there's never been a, you know, definitive, like to, to prove it for all numbers is like a completely different problem

Matt:

Right, right. But each, each, any incarnation, but that's, that's a really interesting point, which he, I think he kind of almost, uh, he almost glosses over that distinction between the fact that proving the goldbark conjecture and checking a particular instance of the goldbark conjecture are two totally different animals. Like,

jon_pt1_raw:

Yeah.

Matt:

Checking it is, is a, is a simple thing. Right? Uh,

jon_pt1_raw:

yeah, relatively trivial little program you can write.

Matt:

um, but, you know, proving it, that's been, uh, that's been keeping us busy for a little while. Um

jon_pt1_raw:

yeah, and so he sort of ends this discussion, or I, I, not end, but he, he throws out a provocation at one point that I thought was very interesting. He basically asks the question, are all number functions primitive recursive? You know, like he basically proves that the Goldbach conjecture is primitive recursive. And he's like, are all number functions this way?

Matt:

Right, right. Exactly. And in other words, like, can we always have a bounded technique of finding. the answer to, to a particular numerical question, basically. Um, and I think, um, well, so, there, you, I'm, if you'll allow me to, like, just, uh, trample on your perfect, uh, like, kind of, cliffhanger. There was one, there was one thing, uh, that I looked up. I was just very curious, because he talks about test. And test is, like, the word, the word test. Um, is, is a very interesting word because you can use it like in programming when you're talking about testing, it is basically just like the, the, the purest definition is like checking the truth value of something, like testing something is like, is it true or is it false? Like if you're testing a number for primeness, you're just determining whether or not it's prime. Uh, And I was very curious, but there's, there's this more colloquial definition, which is like automated testing, like you're writing a, but that's kind of basically doing the same thing, right? Just checking the truth value of, of a series of statements. Uh, but what I was curious to learn is like, where did that, that term come from? Like, where did the term test come from? And if you look, it originally meant like a, an earthenware pot. Uh, so I was like, okay, I'm not really, it's not really clear to me how, you know, how this is getting to like an evaluation of something.

jon_pt1_raw:

Yeah.

Matt:

And when that starts to happen is in like kind of a metallurgical context where if you have a, if you have a metal that you want to evaluate the quality of, you will put it into a test. Like into this earthenware pot in order to evaluate. So you'll say like, put it to the test. Uh,

jon_pt1_raw:

wow.

Matt:

And then that is when it starts to get this kind of more general, like, okay, you're evaluating the quality of something. So, um, I just wanted to add that, that little, little etymological nugget.

jon_pt1_raw:

That is fascinating. Now, I'm still a little confused why putting metal in an earthenware pot like, tests anything.

Matt:

Right, right. That I was not, I'm not able to describe why that does, but I think the idea is you're putting it into a Context which will reveal some some property some desirable product property because I think you're probably taking it out of like the The crucible like because you're probably if you're smelting metal, it's probably in some other Metallic container and then you have to put it. I don't know put it take it out of the I'm guessing here. I should, let's, let's call this. I'm just completely speculating. so anyway, uh, but that's, I just, I did, uh, I did want to, just call that one little thing out and actually maybe this doesn't need to make it into the, into the podcast, but that, that picture that I sent you, the, the urchin.

jon_pt1_raw:

Yes! Yeah,

Matt:

was, those are urchin tests. And anyway, like that thing is in the middle of the like etymology, etymology page of the word test.

jon_pt1_raw:

Oh my god,

Matt:

uh, which it's just this incredible, like, I don't know if there's one picture to this, to capture the, the beauty of biology. I feel like, I feel like it's this, uh, this picture, but,

jon_pt1_raw:

Yeah, Matt randomly sends me this image of like, well, yeah, just like you were saying, it was some creature, uh, some sort of like undersea sponge or coral or something that was perfectly geometrical, this sort of semi spherical shape with these like circular portals on it. Uh, just looked really cool.

Matt:

if we're going back to, back to the original, it was this, it was this dance of order and chaos, uh, just like, just like number systems.

jon_pt1_raw:

Nice.

Matt:

all right, but we will, this was the first chapter, first half of chapter 13. And, um, and then, yeah, we will actually, you know, to get back to John's, uh, John's setup, we will answer the question. Can any numerical function be, uh, be, or is every numerical function primitively recursive?

jon_pt1_raw:

All right. See you next time, Matt.