Week 3: An Algorithm for Killing People
CS198–79 Philosophy of Computation Course Notes
1. The Seemingly Unbreachable Gulf
The goal of this course is to question the commonly assumed dichotomy between the subjective and the objective.
In the preface to his classic, Godel, Escher, Bach, Hofstadter writes:
In a word, GEB is a very personal attempt to say how it is that animate beings can come out of inanimate matter. (p. 2)
The Godelian strange loop that arises in formal systems in mathematics is a loop that allows such a system to … acquire a self. (p. 3)
One of the major purposes of this book is to urge each reader to confront the apparent contradiction head on, to savor it, to turn it over, to take it apart, to wallow in it, so that in the end the reader might emerge with new insights into the seemingly unbreachable gulf between the formal and the informal, the animate and the inanimate, the flexible and the inflexible. (p. 26)
This “seemingly unbreachable gulf” is like the so-called “metaphysical gap” we have discussed in week 1. Hofstadter believes there is a way to bridge this gap. He names the bridge a “Strange Loop.”
Now if Hofstadter is right, this would be an amazing breakthrough: it would basically solve the problem of consciousness and the mind-body problem, a mystery that has haunted humanity for millennia. So what is this mysterious Strange Loop? It must be something profound! But at first sight, it seems like stupid wordplay by a 4-year old.
2. Strange Loops
Consider this sentence:
This sentence is false.
Now, is this sentence true or false? Let’s say it’s true (we think it’s being honest): then, because it says it’s false, and we think it’s being honest, so its assertion must be correct, and it must be false. Let’s say it’s false (we think it’s lying): then, because it says it’s false, and we think it’s lying, so its assertion must be incorrect, and it must be true. We are stuck in a situation where we can’t say the sentence is neither true nor false. Any attempt to do so will just backfire into a contradiction. This is one instantiation of a Strange Loop, also called the liar’s paradox, or the Epimenides paradox.
Q: Why do we let ourselves get caught in such a loop? Why can’t we just disallow this sort of loopiness?
Great question. The critic may say: clearly there is something pathological about a sentence that refers to itself, and we should just ban them altogether. In fact, Bertrand Russell, a towering figure of 20th century mathematics, agreed with you totally, and dedicated his life to destroying strange loops! But this might be harder than it seems, because the strange-loopiness might be hard to locate:
The following sentence is false.
The preceding sentence is true.
Hofstadter says:
Taken together, these sentences have the same effect as the original Epimenides paradox; yet separately, they are harmless and even potentially useful sentences. The “blame” for this Strange Loop can’t be pinned on either sentence — only on the way they “point” at each other. (21)
Well, one might say, it’s still pretty simple to detect, it’s just that we must ban thinking about both sentences together; what’s the big deal? Consider now that the Strange Loop may be buried across not just two but hundreds of thousands of sentences. Some of them taken together may cause Strange Loops; some of them might not. So it is harder to detect Strange Loops than one might expect.
Q: A Strange Loop seems pointless. We’re just stuck in a loop going back and forth and back and forth. There’s no end goal. It’s like we’re stuck. It’s like it’s static.
That’s a very interesting point. When reading a sentence, oftentimes one has an impulse to say the sentence is true or false. This may be so ingrained in one’s mind that one may think the entire point of a sentence is whether it is true or not. (Frege, a logician and philosopher of language, thought exactly this, and dedicated his life to showing this… only to be devastated by Godel’s proof.)
But Hofstadter thinks the opposite: for Hofstadter, Strange Loops don’t drain meaning, they cause meaning! According to Hofstadter, Strange Loops allow something “as selfless as a stone or a puddle” to “perceive itself”, to “become self-aware”, to “acquire a self”.
Again, we see two completely contradictory ways of thinking about meaning. Earlier, we saw: it seems like meaning is in randomness, but it also seems like meaning is in reason, the opposite of randomness. You, as well as Frege, said Strange Loops are meaningless, but Hofstadter said they are the very essence of meaning. Again, what is meaning and where is it?
3. Bertrand Russell and Self-Swallowing Sets
A little history. Bertrand Russell was this guy who absolutely hated paradoxes. Russell wanted a iron-strength system of math free from all contradictions. So he spent ten years writing Principia Mathematica, a fortress of math specifically designed from the ground up to banish all Strange Loops forever and ever. Specifically, he hated self-swallowing sets, and wanted to get rid of them.
There seems to be something wrong, something evil, something pathological, about a set that contains itself. So it might be nice to divide all sets into two sets: (1) the set of sets that don’t contain themselves, and (2) the set of sets that do contain themselves. Hofsatdter calls the set of sets that don’t contain themselves “run-of-the-mill sets”, because they seem like the more normal, non-pathological, sort of sets we talk about when we talk about sets. Example: the set {1, 2, 3}. Clearly this set doesn’t contain itself. Hofstadter calls the set of sets that do contain themselves “self-swallowing sets”. You may imagine a person with his/her lips around him/herself, legs and feet and all fit snugly inside. Clearly, s/he seems pathological; if you’re set up for a blind date with someone, wouldn’t you like to know whether they have their puckering lips around themselves or not? In the red basket (normal society) I want to throw in all the run-of-the-mill sets (normal people), and in the blue basket (prison) I want to throw in all the self-swallowing sets (people with their lips around themselves). Now here’s a problem. What about “the set of all run-of-the-mill sets” (a person swallowing all the normal people)? Is this set a run-of-the-mill set, or is it a self-swallowing set? It it’s a run-of-the-mill set (a normal person), because it’s supposed to contain all run-of-the-mill sets (all normal people), it must contain itself, and therefore it must be a self-swallowing set (the person must swallow him/herself as well as everyone else). But then it is no longer the set of all run-of-the-mill sets, because it contains a self-swallowing set, namely, itself. So it can’t be a run-of-the-mill set (Not normal!). But if it’s a self-swallowing set, because it contains itself, it must have itself inside of it (If the person has his/her body inside his/her stomach, this person must contain him/herself). Then again, it is a self-swallowing set, and since the set is supposed to be the set of all run-of-the-mill sets with no room for a self-swallowing set, (remember, this person is supposed to only swallow normal people, but it swalllows his/her very abnormal self) this is impossible. So it can’t be a self-swallowing set.
It can be neither, and this can only mean that we can’t sharply delineate the two sets of sets. In other words: given an arbitrary set, one cannot know if it is self-swallowing or run-of-the-mill! This is horrifying, because it means there is absolutely no way to tell if a set is infected with this pathology — there is no way to tell if the person you’re about to go on a date with is a normal person, or some weirdo who’s curled up in a ball, the inside of her/his mouth oozing slime all over her/his body.
Q: What about the example you just cited, {1, 2, 3}? Clearly this is a run-of-the-mill-set. But didn’t you just say that we can’t decide if a set is self-swallowing or run-of-the-mill? So how can we decide that {1, 2, 3} is a run-of-the-mill set?
The catch is the word arbitrary in “given an arbitrary set, one cannot know if it is self-swallowing or run-of-the-mill”. While it usually means the same thing as “a”, the word arbitrary as used here is a somewhat technical term, though it is somewhat difficult, maybe impossible, to define. Usually, arbitrary in math means: whatever you want. It is almost a psychological term. If I say that I’m thinking of an arbitrary number, that means I’m thinking of a number I want to think about. It strongly connotes that you, who are not me, can never know what number I am thinking of. One might say: “this program is secure to arbitrary attacks.” This means that whatever the attacker does, the program is secure. The key is that we don’t know what the attack might be, cannot put them in a list, cannot put them all in a basket. In our example, we can tell {1, 2, 3} is run-of-the-mill because it is not arbitrary, but specific. I wrote it down: the set we’re dealing with is exactly {1, 2, 3}. But if I say we’re dealing with an arbitrary set, all I’m telling you is that it’s a set, nothing about what the set looks like, no property whatsoever about the set. One can think of it like: a specific set has more information, but an arbitrary set has less information, therefore there’s less one can deduce about an arbitrary set than about a specific set. But having a way to decide if a specific set is self-swallowing or run-of-the-mill is of no use. We want to find a way to decide if any set is self-swallowing or run-of-the-mill, with no other information about the set given to us other than that it’s a set. And this is a much harder, even impossible, problem.
Russell was tortured by this problem. He thought, if math could not filter out these pathological items, math cannot rest on a secure foundation, and nothing we know about math could be absolutely true. After a decade of wrestling with this problem and going nearly insane, Russell published the tome Principia Mathematica. But the ideals of the book, securing a foundation for mathematics free of contradiction, was utterly shattered when Godel published his Incompleteness theorems.
Russell was devastated. But he had a baby, chilled out, entered an open relationship, and spent the rest of his life arguing for peace in a world gone mad with the second world war. He also managed to mentor one of the greatest philosophers of the time, Wittgenstein.
In the interest of time, I had to give you a cartoon-caricature version of Russell, but he actually led a good and fascinating life. If you want a visceral idea about his life and Godel’s Incompleteness Theorem in its full historical context, I highly recommend the comic book Logicomix, which starts with Russell giving a speech advocating for peace during World War II right here at UC Berkeley.
4. The MU-Puzzle
In section 1, we said we want to talk about bridging the gulf between the formal and the informal. So let’s first make sure exactly what we mean by “formal” and “informal”. This brings us to the first chapter of GEB, the MU-puzzle.
The MU-puzzle gives you a flavor of what it is like to do formal reasoning. The system looks like this.
· Axiom: “MI” is given.
· Rule 1: If you possess a string whose last letter is “I”, you can add on a U at the end.
· Rule 2: Suppose you have Mx. Then you may add Mxx to your collection.
· Rule 3: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.
And the challenge is to create the string “MU”. This setup illustrates some important points. First: all formal systems need some axiom(s), which are unquestioned bedrock assumptions. Which is already interesting: some may think of formal reasoning as reasoning free of any and all assumptions, but that is not true. We can’t get off the ground if we have no ground to get off of. We have to start somewhere. (Lakoff would probably say that this “somewhere”, the ground, is the body…)
There’s a famous episode about this idea, which may seem somewhat sexist, or anti-sexist, depending on how you look at it. Some famous scientist is giving a lecture on the origin of the Universe. An old woman in the audience raises her hand, and, disagreeing, says, “I see your theory, but it’s wrong. The Universe is actually supported by a giant turtle.” The scientist, cynically amused, says, “OK, my dear, then what is the turtle supported by?” And the woman says, “The first turtle stands on the back of a second turtle, which is much larger.” “OK, what does the second turtle stand on?” “You think you’re so smart, Mr., but it’s no use. It’s turtles all the way down!”
The woman has a salient point: without some assumptions to stand on, we cannot avoid infinite regress. In this way he’s pointing out a logical hole in the scientist’s theory: sure, you can come up with a theory about the origin of the universe, like the Big Bang, but what caused that? To avoid this we need baseline assumptions. An axiom is such an assumption to stand on. (This idea pops up again in Week 4, in Two-Part Invention.)
Second, rules describe how we start from the axioms to get to new theorems. The axiom gives us the ground, but there’s no use sitting around doing nothing on the ground. We’d like to flutter up and reach the stars. The rules give us ways of fluttering upwards. Rules are, as axioms, assumed to be true. Hofsatdter challenges us to reach one such star in this formal system: “MU”. Can we reach it?
If you’ve tried it, you may have become frustrated, and had an inkling that it was impossible. Indeed there is no way to get to “MU” in this system. And here is another important point: if we asked a computer to solve this problem, it would never, ever stop, and would never recognize that it can’t get to “MU”. In other words, humans can “jump out” of the system, while computers can’t.
It is an inherent property of intelligence that it can jump out of the task which it is performing, and survey what it has done … For example, a human being who is reading a book may grow sleepy. Instead of continuing to read until the book is finished, he is just as likely to put the book aside and turn off the light. He has stepped “out of the system” and yet it seems the most natural thing in the world to us. … of course, there are cases where only a rare individual will have the vision to perceive a system which governs many people’s lives, a system which had never before even been recognized as a system; then such people often devote their lives to convincing other people that the system really is there, and that it ought to be exited from! (p. 37)
5. An Algorithm For Killing
Suppose it’s 2020, and Uber’s new self-driving car has to decide whether to kill person h1 or person h2. The two people are directly in front of the car, and the car can turn slightly left to hit h1, or turn slightly right to hit h2. If it does nothing, both people will die. What should the car do? Rather: how should Uber’s software engineers program the car to act in such a situation?
Here is one way. The car performs facial recognition on h1 and h2 and matches their faces with their Facebook, LinkedIn, Twitter accounts, as well as secret governmental databases. Then it retrieves how much money they earn, where they live, their jobs, their ethnicities, their gender identities, where they’re from, their families’ information, and so on. Then it runs a machine learning algorithm to decide whose family is more likely to sue Uber should the car kill their family member. Say person h1’s family is rich and powerful, and will sue with 90% chance, while h2’s family is just a pleb, and will sue with 4% chance. Therefore the car kills h2.
This may sound far-fetched. But a machine learning algorithm that, to a significant degree, decides who lives and who dies already exists: the US military uses one to kill people in Pakistan with Predator strikes.[1] Given the current ethos of Silicon Valley, I’m not too sure if it’s far-fetched to say Uber, or Google, would do something like this. In fact, I think it’s naïve to think they wouldn’t do something like this. Uber’s operating method so far has been to ignore every regulation and law, abuse every good will and benefit of the doubt, to become as powerful as it can. Who’s to say they won’t do the same thing again?
But I think this is bad. I think we should have a way to say that no algorithm can exist whose methods can justify who’s to live and who’s to die. Of course, many may disagree. One can formulate this debate in a succinct way:
Does (should) the following algorithm exist?
IF f(h1) > f(h2), Kill h1
OTHERWISE, Kill h2
where f is a function that maps from H, the set of humans, to the set of rational numbers
Q: Clearly this algorithm exists: you just said it does, the one the US military uses.
Right, I did. I’m using “exist” in two different senses. When I said that such an algorithm exists and the US military has one, I meant “exist” in the normal, everyday sense of the term: they have developed this algorithm, and they use it to kill people. But when I ask if the algorithm exists in the above italicized question, I mean “exist” in a mathematical sense. If I say, “does there exist an algorithm that says 1 + 1 = 3?” one might reply, “yes; my 2-year old cousin uses just that algorithm to add numbers.” But clearly, in this case, one’s cousin is wrong; there exists no algorithm that says 1 + 1 = 3, because an algorithm is supposed to be correct, and a wrong algorithm is not an algorithm at all. It is in this sense that I ask, does this function exist? Can there exist some mathematically sound function that takes as input a human and outputs a number?
Here is an argument for why no such function can exist. Hofstadter says that a human can jump out of a system. Whatever the function f is, it must be computed inside of some formal system. So if Hofstadter is right, a human can never be contained inside of a system, “held still” while f runs it analyzing gaze up and down his/her limbs. The human is capable of jumping out the system! To be a little more precise, Hofstadter says a sufficiently powerful formal system is capable of “perceiving itself”, of “talking about itself”, of “being self-aware”; so we can say a human is such a sufficiently powerful formal system, and there are truths about a human that cannot be found by any method while working inside of any system. f, being an algorithm, must work inside one such system. Therefore, f cannot exist!
Q: When you say f must “hold still” the human, it seems like you mean that f needs to have the human as unchanging. What if the computer has a series of representations of the human over time?
In this case, a human h1 would be represented as some series over t time steps: [h11, h12, h13, …, h1t]. But in this case, the computer still has an “unchanging” representation of the person: the information comprising the entire series does not change.
Q: What about a supercomputer that’s much faster than a human, and can predict his/her every move?
Great question: the speed of predicting seems to play an important factor here. In fact, you are right: a chess-playing supercomputer, for example, is much faster than a human, and can look several more steps ahead than any human can. Today, there is almost no hope for any human to beat a supercomputer in chess. But that’s because the human is playing inside the system. The human can “exit the system”, walk up, and unplug the computer.
Q: What if the computer is so powerful it knows how to defend itself from that?
Then the computer might kill the person, but this doesn’t mean the computer will win. The person can still “exit the system” — he can die! Besides, we’re getting further from the original argument. The argument wasn’t that: computers can’t beat humans in anything, ever. They clearly can! The argument wasn’t even that: computers may beat humans in some domains, but not all. They might, someday. The argument was, rather: if one is committed to the idea that humans can “jump out of a system”, then one cannot avoid the conclusion that some f that takes as input a human and outputs a meaningful rational number cannot exist. By meaningful I mean the function captures something nontrivial about the human. This clause is necessary because it is very easy to design a function f that takes as input a human and outputs a meaningless natural number: say, take the first character of the person’s name, and output the number that looks most like that character. By meaningful, I mean more precisely, the function f must take into account not just the syntax but the semantics of the person; it must take into account the output of the person. And it is impossible for f to do this, because the person can “jump out of the system” and give an output f could never predict.
[1] https://arstechnica.com/information-technology/2016/02/the-nsas-skynet-program-may-be-killing-thousands-of-innocent-people/
