## (1,5): And He Called 0: They needed a doctor. Mathematics was sick. So they called this guy. ![[david-hilbert.jpg]] 0: Doctor Herr Professor the esteemed David Hilbert. See him? 1: _(Still a bit disoriented)_ Yeah. 0: There's your doctor. 1: _(Silently recovering)_ ... 0: The perfect one for the job. They called him. 0: And he called everyone. Called them together. All the mathematicians. A call to arms, in 1900. He was the sort of guy who could just come up with a list of questions for an entire field to work on, and then everyone would agree that's the agenda. He said "Ok every one here's the deal. We've got some problems and I want you all to solve them. Here's the list." And then he reaches under that big hat and pulls out the following list: ![[hilberts-problems.png]] 1: _(Feeling a bit better)_ Which one is the one about how mathematics is broken? 0: Look closely and see if you can find it. 1: Oh! The first one. About Cantor. 0: Nope. Not that one. 1: Hmm... I don't see anything about comprehension or Russell's paradox. How is 4 on there? Math is weird. 6 sounds hard. I don't know, I don't see anything about mathematics being broken on here. 0: It's 2. 1: What? 0: And also 10. 1: How is it--- 0: They're basically the same. 1: How are 2 and 10--- 0: Y'know. Binary. 1: No bad puns please. I'm still a bit dizzy from all the gotos. 0: Yeah those are considered harmful. Anyways back to Hilbert and his problems. ## 0b10111 problems but a bit ain't one 1: _(Looking sick again)_ 0: Anyways, naturally, 2 and 10 are basically the same thing and this would soon lead to the creation of computing as a field. 1: Woah really? 0: Yep. 1: How did THAT happen? 0: Ok so, problem 2 is the one that was motivated by Cantor and Russell. Everyone knew there were some serious bugs in the foundations. But just like in software, you can't just stop the world to fix a bug. Mostly, people just ignored it. 1: Ignored the bugs? 0: Exactly. But folks like Hilbert cared about the foundations. 1: Was Hilbert the first of the Foundational People? 0: Not really. I mean it wouldn't be so wrong to put him in that camp. He cared about the foundations, but he cared about everything. He was very much a mathematician's mathematician. He fit in well with the crowd. So much so that he sort of became their leader. He was sort of like the CEO of mathematics. And in the legends about this period, he's made out to be more of the kind of guy who'd get accused of doing "theology" (i.e., vague mathematics) than the type who'd get accused of being too concerned with foundations. He was both. Here's a clip from a paper that explains some background.[^1] [^1]: From _Hilbert on Theology and its Discontents: The Origin Myth of Modern Mathematics._ By Colin MCLarty. ![[hilbert-theology-myth-4.png]] 1: I almost fell asleep. Did I miss anything? 0: Oh c'mon I deleted irrelevant bits and everything. The point is that Hilbert was sort of the Director General of mathematics, plus the bit at the end. "Without actually finding these systems, Hilbert proved... they exist." That's a non-constructive existence proof, and it's very much a signal that he's a classical guy. A mathematician's mathematician. Not someone who would choose foundational concerns over mathematics. Faced with a choice, Hilbert chooses mathematics first. Even in ways that made the old-timers suspicious. ![[hilbert-theology-myth-3.png]] 0: See non-constructive existence proofs weren't always a common thing. But once they started, it was hard to stop. They made mathematics so much easier. And Hilbert would always choose mathematics. 1: Is there a point to this story? 0: Getting there. Ok so in his big list of problems, Hilbert mostly listed standard mathematical questions. But he threw a bone or two to the foundational questions too. Specifically, 2 and 10. > Problem 2: Are the axioms of arithmetic consistent? > Problem 10: Something about "Diophantine equations" that seems totally irrelevant. 1: I was about to say I don't see why 10 is relevant. 0: Good. It's not clear at first glance. But here's problem 10 expanded out in more words: ![[hilberts-10th-problem-1.png]] 1: What's a Diphanotine equation? 0: Diophantine equation. A "Diophant" is a large animal made from an integer num--- 1: Stop. 0: Ok it's a polynomial with integer coefficients and any number of unknowns. 1: I need an explanation halfway between those two. 0: Ok so, they want someone to write a function that eats any Diophant and spits out a boolean. And Diophants are a type of function. They're not just any function, just a specific species. For example, here's one of the Diophants: $x^7 + 12x^5 + 42x^4 + 2x + 3 = 0$ 1: Ok. 0: Here's two more. $x^{1010101} + 2 = 0$ $x + 2y + 3z + xyz = 0$ 1: What kind of functions don't count as Diophants? 0: Lots. For example, these aren't Diophants: $\sin(x) = 0$ $e^x - 5 = 0$ $x^{\log(x)} - \pi = 0$ $x^{1010101} + \frac{1}{2} = 0$ $x^{1/2} + 1= 0$ $x + 2y + 3z + xyz + \frac{1}{3} = 0$ 1: I think I'm ready for the definition. These examples aren't helping. 0: Ok so speaking formally, a Diophant is a large polyanimal with $n$ variables and $\mathbb{Z}$ coefficients, where: - $n \geq 1$ is any natural number. - $\mathbb{Z}$ stands for integer. - animal = nomial. 1: Impressively formal. 0: Thank you. Ok so Hilbert's 10th problem was to write a function that eats any Diophant and spits out a boolean that says... something. 1: What kind of something? 0: Whether the Diophant is solvable. 1: Ok. _(Narrator: Both characters sit in silence for a few moments, each expecting the other to continue.)_ 0: See why this is relevant to computing yet? 1: Not even a little bit. 0: Can't blame you. Here's a hint: ![[hilberts-10th-problem-2.png]] 1: Ooh, ok. Starting to sound like computing. But wait, mathematicians had been providing algorithms for computing stuff for like thousands of years hadn't they? 0: Of course. The problem here was that no such algorithm existed, though nobody knew that at the time. 1: Why is that a problem? 0: Well there had been cases of mathematicians proving that "No such X exists" in response to questions of the form "Find an X that does such and such." For example, the solvability of the quintic. Basically if you make high school algebra problems more and more annoying for a couple centuries until you're trying to solve $x^5 + ax^4 + bx^3 + ... = 0$, eventually a French kid shows you can't solve stuff like that and then gets shot in a duel over a girl. 1: You lost me. 0: Don't worry. Different story. Definitely not one we'll be covering here. The point is that mathematicians had run into questions that sound like "Solve X" and had managed to respond "No, that's impossible" just fine in the past. Even for other questions about polynomials. But this time was different. 1: How is this different? This tenth problem sounds like it's about polynomials too. 0: See where it says "a general algorithm"? 1: Yeah, you highlighted it. 0: How do you prove that "no algorithm whatsoever can exist such that \[blah\]"? 1: I dunno. 0: What's the first step? 1: The first step of showing no algorithm exists such that \[something\]? 0: Yeah, what's step one? 1: I have no idea. Look I came here to learn about computing, I don't know why we're still talking about ma--- 0: Perfect! Come in here. Let's learn about ## Computing! 0: Hilbert's 10th problem in programming terms is to write a function $f$ that eats a Diophant and spits out a Bool that says whether or not the Diophant is solvable. 1: How do you eat a Diophant? 0: One byte at a time. I'll take the bytes on the top and bottom. ```python def f(diophant) -> Bool: ... return answer ``` 0: Now you finish the middle. 1: What's a Diophant again? 0: It's any: > ... polyanimal with $n$ variables and $\mathbb{Z}$ coefficients, where: > - $n \geq 1$ is any natural number. > - $\mathbb{Z}$ stands for integer. > - animal = nomial. 1: So it's a list of int? 0: How so? 1: Like if I had to represent a polynomial like this: $f(x) = x^5 + 2x^3 - 6 x^2 + 10x + 7$ but in code, I'd just represent it as: ```python f = [1, 0, 2, -6, 10, 7] ``` 1: The length of the list is one more than the highest power, and whenever a power is missing you just put a zero in the list. 0: Ok but the original $f$ was a function. How do you "plug something in" to your list representation? 1: Easy. Whenever I need $f$ as a function, I can just do this: ```python def mkfunc(diophant): def func(x): pocos = enumerate(reversed(diophant)) terms = [co*pow(x, po) for po, co in pocos] return sum(terms) return func ``` 1: Now clearly: ```python >>> f = [1, 0, 2, -6, 10, 7] >>> F = mkfunc(f) >>> F(0) 7 >>> F(1) 14 >>> F(2) 51 ``` 1: And so on. And I know these things can have multiple variables but I'm gonna start with one variable and worry about the more complicated Diophants later. 0: Great! Extremely nerdy and a very good start. Now how do you get the bool? 1: What bool did we want again? 0: The bool that says if the Diophant is solvable. 1: What does "solvable" mean again? 0: Whether or not there's any $x$ that makes the function return $0$. 1: What type is $x$ allowed to be? 0: Just integers. Let's keep it simple. 1: Positive only, or positive and negative? 0: Positive and negative. 1: Can't I just loop over them all and check? 0: How so? 1: Like this: ```python def solve(diophant): f = mkfunc(diophant) n = 0 while True: for x in (-n, +n): if f(x) == 0: return x ``` 1: It checks 0 twice but 0 is a pretty suspicious number, it's important to check it twice to make sure it's not up to something. 0: There are like $\omega+2$ problems with this code. 1: Is that "infinity plus two"? 0: Yes. 1: What problems exactly? 0: Well: 1. You forgot to increment $n$ each time around the loop. 2. You're returning the $x$ that solves the equation, you were supposed to return a bool. 1: Ok sure, what are the other "infinity" problems with my code? 0: What if $f$ doesn't have a solution? 1: _(Looks back at the definition)_ ... Then it loops forever. 0: Right. So after fixing 2 out of your infinity plus two bugs, we've got this: ```python def solve(diophant): f = mkfunc(diophant) n = 0 while True: for x in (-n, +n): if f(x) == 0: return True n += 1 return False ``` 0: Not exactly a solution to Hilbert's problem. 1: Why can't we just do what Cantor did? 0: Lose our minds and die alone? 1: No I mean if he can loop "past the dot-dot-dots," why can't we? 0: How do you suggest we do that? 1: I dunno, it wasn't a serious answer. I see why this isn't going to work though. 0: So what would you do next? 1: Not sure. We have to do something more clever than just checking all the numbers. I mean if there is a solution, we'll find it once we get there. But if there isn't a solution, we won't find it once we don't get there, because we don't get there, because there's no "there" there. If there's no solution, we'll just loop until mathematics gets hot and overheats and shuts down. 0: So how do we solve the problem before mathematics overheats? 1: Meaning? 0: In finite time. 1: No idea. But I'm definitely sure the problem feels like math now. 0: Exactly! And Hilbert's problem is sort of like a Diophant. 1: What? 0: Well look back at the problem statement. ![[hilberts-10th-problem-2.png]] 1: How is this like a Diophant? 0: Obviously! ```python def solve(hilbert_problem): fs = mkalgorithms() while True: for f in fs: if hilbert_problem(f) == 0: return True return False ``` 1: This is the stupidest code I've ever seen. 0: Well it's pseudo-code, but--- 1: Still stupid. 0: I don't see why it's all that different from yours. 1: Wtf is `hilbert_problem(f) == 0` supposed to mean? 0: Well in the Diophant case `f(x) == 0` meant "x is a solution of f". 1: Yeah. 0: So naturally `hilbert_problem(f) == 0` means "f is a solution of hilbert's problem." 1: Ok fine. That's still ridiculous, but let's assume for the sake of argument that we can somehow write a checker type of meta-algorithm that takes any algorithm and tells us if it's a solution to Hilbert's problem. 0: Glad you're finally seeing things my way. 1: Not there yet. What the hell is happening on this line? ```python fs = mkalgorithms() ``` 0: That's a function that returns every possible algorithm. 1: Zero, that's insane. 0: Why? 1: Because that function is never going to return. 0: Why not? 1: There are infinitely many things in there! 0: So, we can write this no problem. ```python def mknumbers(): n = 0 while True: yield n n += 1 ``` 0: If we need to loop over all the numbers, just make it a generator instead of a function. 1: You know that's not the problem I have with your code. 0: Still not understanding the problem. 1: You're really not? 0: I didn't say _I_ wasn't understanding. 1: What? 0: Do you see the fundamental similarity between your code and mine? 1: I mean yours looks similar to mine. Yours is insane though. 0: In what sense? 1: Define algorithm. 0: Very insightful! But that's not what I meant. 1: What's not what? 0: Your code was perfectly well defined, but it had a problem. What was it? 1: That if there was a solution, we'd find it. But if there wasn't one, we'd loop forever. 0: Exactly! Now what's the problem with my code? 1: Well, one problem among MANY is you didn't implement `mkalgorithms()`, and even if you did, it would have to loop over every possible algorithm and that's insane. 0: Let's suppose we can implement that. 1: Ok so we're assuming we can somehow loop over _every possible algorithm_, and we're also assuming we've already written the code in this line ``` hilbert_problem(f) == 0 ``` which takes any algorithm as input and then checks if it solves the problem. What was the problem again? 0: Hilbert's 10th problem. So `hilbert_problem(f) == 0` if and only if `f` solves the _"Does this Diophant have a solution?"_ problem for every possible Diophant. 1: This is too many levels of insane. 0: It's really not! Just trust me for one minute. I'm trying to show you that _if_ we assume we've implemented those two little bits that are bothering you for some reason, _then_ I'm suggesting my code is fundamentally the same as your code, in the sense that it has the same problems as yours and no more. 1: _(Reluctantly)_ Ok, if I grant all that, how exactly does my super reasonable code have the same problems as your totally insane code? 0: Well, let's look at it: ```python def solve(hilbert_problem): fs = mkalgorithms() while True: for f in fs: if hilbert_problem(f) == 0: return True return False ``` 0: What happens if there's a solution? 1: We'll find it eventually, in the imaginary universe where this makes sense. 0: What happens if there isn't a solution? 1: We'll loop forever, same as my code. 0: Exactly! 1: Exactly what? 0: You said it yourself. > _"same as my code."_ > -One, aka 1, in a rare moment of wisdom 1: I hate you. 0: No you don't. But you are starting to see I was right! 1: About what? 0: That it's the same problem in both cases. 1: Why is this problem even interesting again? 0: Define algorithm. 1: You want me to defi--- 0: No. I mean that's why it's interesting. 1: "Define algorithm" is why it's interesting? 0: Exactly. Hilbert's 10th problem didn't sound interesting on the surface. Maybe it is to mathematicians, but not to the Foundational People. 1: How _do_ you define algorithm by the way? 0: Great question. 1: You're not gonna answer me are you. 0: Not yet, but we're getting there. 1: Why do I feel like that's your answer to everythi--- 0: You can prove that there's no real number that solves $x^2 + 1 = 0$ because the search space is just the real numbers. You can prove there's no solution to the quintic because the search space they cared about was just the stuff you can do in high school algebra: namely functions that can be expressed in terms of $+$, $-$, $*$, $/$, and fractional powers like taking square roots, cube roots, $n^{th}$ roots, etc. For the quintic, the search space was a very limited kind of function. 1: Sort of following. So what? 0: What's the search space of possible solutions you have to check if the question asks you to find a general algorithm? 1: All algorithms? 0: All algorithms. 1: Oooooooh. That's the thing you pretended you could loop over. 0: Exactly! So thanks to Cantor and Russell, the effective CEO of mathematics has now put a bounty on the following two problems: Problem 2: Prove that arithmetic is consistent. Problem 10: A question that asks you to find _any algorithm_ that does a thing. Problem 2 is definitely about the Foundations of Mathematics. Problem 10 _might be_ about the Foundations of Mathematics. 1: Might be? 0: It's not clear from the problem statement. Think about it. - If some solution exists to Problem 10, then Problem 10 is just normal mathematics. Loop over all the algorithms until you find it. Or equivalently, just wait and do nothing until some smart nerd finds a solution. That's how you loop over all the algorithms by the way. Just sit and wait and do nothing, and the nerds of the world are guaranteed to find it. Works every time. But!... 1: But what? 0: - If no solution exists for Problem 10, then you somehow have to say something about _the space of all possible algorithms._ Now it turned out that Problem 10 didn't have a solution. It wasn't solved until 1970. But already by 1935, it had started a revolution in the foundations of mathematics that would eventually become our field. 1: Ok, I'm awake. Can we be done with the math stuff and get to computing now? 0: Perfect timing. That's exactly where we're heading. 1: Where? ## Computing\\!\\! 0: To a place with so many restrictions and constraints that you'd expect it to be completely devoid of fun. 1: School? 0: More rules than that. 1: Work? 0: Way more rules than that. 1: I dunno, where? 0: Formal systems. 1: Huh? 0: Formal languages, and the formal theories built on top of them. Those objects studied by a strange culture we mentioned in passing a while back. 1: The language people? 0: That's them. 1: The ones who study made-up languages with infinitely many axioms? 0: Those ones exactly. Rule after rule after rule after rule. 1: Sounds like a pain. 0: Usually that sort of thing is a pain! But it turns out these formal systems, despite all their restrictions, don't have the typical feel of a system with lots of restrictions. They don't feel like some high priest standing up and saying: - You may eat any animal that has a divided hoof and that chews the cud. - There are some that only chew the cud or only have a divided hoof, but you must not eat them. - The rabbit, though it chews the cud, does not have a divided hoof; it is unclean for you. - The pig, though it has a divided hoof, does not chew the cud; it is unclean for you. 1: What is this, some kind of logic puzzle? 0: No that's Leviticus. 1: What's Leviticus? 0: The part of the Old Testament that's just rules rules rules over and over and over and over and over and--- 1: I got it. 0: Formal systems seem to have an equally prohibitive number of restrictions. I mean when you first try to use one, it feels like everything you want to do is illegal. 1: Sounds hard. 0: It's actually not. I think you'll enjoy it. 1: What makes you think that? 0: We've already seen some of it. 1: When? 0: The first code. 1: Ooooh that! 0: But things are gonna feel pretty unfamiliar once we're there. 1: I think I can handle it. I'm a professional devel--- 0: Whenever you're ready. 1: Are we heading to another file? 0: Yep! Time to leave. File #6! 1: Can we stay here? I'm still feeling a bit sicks from all the context sw--- 0: Perfect! Time to leave. goto: [[lost+found/2/1|Exodus Sicks]]