An Undecidable Bender

—What types of questions can a bender answer? The existential implications of a simple question.

Published: Saturday, October 24 2015 14:02

Written by Jesse Riggs

Fry's Question

Writer and director of American classic, The Simpsons and sci-fi-spoof, Futurama, David X. Cohen stands as one of my favorite creative talents. Not only is Cohen a four-time Emmy-winning cartoon creator, but he also has a strong science background. In 1988, Cohen received his Bachelors in Physics from Harvard University, and then attended UC Berkeley where he earned a Masters in Computer Science. His comedy is often sprinkled with geeky nuggets of math, science and philosophy. I often find myself pulling apart layers of meaning throughout his work. But then my friends tell me that I’m looking too deeply into children's cartoons.

However, today, I am sharing a problem, proposed in the first episode of Futurama, which illustrates a startling truth about the limits of knowledge.

Trapped inside a head-museum, Fry begs Bender to perform a simple life-saving task.

Now, without opening a can of worms around free-will and determinism, I would like to bring your attention to a peculiarity in Fry’s question; an anomaly, from which a master of computer science could define the edge of a universe.

More specifically, a bender who can answer this question—as it turns out—is very special. Such a bender could be programmed to give us many useful answers to questions that fall outside our grasp of understanding. Given an strand of DNA, this bender could tell us if it’s not a virus. We could give him two different languages, and then he could tell us if there is no common sentence shared between them. He could tell us if a piece of software will succeed in giving us an answer, or if it will run for ever.

The job of the computer scientist is to build problem-solving machines. But, sometimes, a scientist is given a problem, or set of problems for which they are unsure how to build a solution. At this point, it may be easier to show that any machine that could solve such a problem cannot exist. So, the question becomes “could a bender who can answer Fry’s question even exist?”

How Does A Machine Solve Problems?

The way a machine ( Bender ) solves problems is a lot like the way you play a board game. He is given a set of rules. He then reads some input, like a number on a die, or a card from a deck. And then—according to the rules of the game—he writes a bit of data, such as the position of a game piece, to his memory. He continues this process, repeatedly, until he reaches a final square where the game is finished—and then returns an output: whether he won or lost the game; yes or no.

Decidable Problems

There are an infinite number of problems that can be decided(answered) either yes or no, such as: “are there 10 Jellybeans in the jar?”, “is ten equal to ten?” or “is Jellybean equal to Fruit Loop?”. We can show that such problems are decidable by constructing a set of steps that will always arrive at a solution of either yes or no. For example, we will stack ten blue poker chips on top of a single red poker chip. For each Jellybean in the jar, we will eat it and then throw away one poker chip. If, when the Jellybeans have all been eaten, there is a single red poker chip on the table, we then know there were ten Jellybeans in the jar. This set of steps is called an algorithm.

To further broaden our horizon on the set of decidable problems, we can change the parameters of a decidable problem into variables, such as X and Y, to create a new decidable problem. Examples will include: “are there X Jellybeans in the jar?” and “is X equal to Y?”. But, not all problems can be solved with algorithms.

Undecidable Problems

Consider Problem 1, is this statement true or false? When we assume that this statement is true—since it says that it's false—it must be such; false…? But, when we assume that it is false—since the statement says that it is false—it must be false that it is false. So, it must be true…? Maybe, in a metaphysical sense it is both true and false. But, in the material world, nothing can be measured as both true and false, at the same time. This is a contradiction↯. So, we cannot build a machine that answers this question. This problem is called undecidable.

The whole universe is full of undecidable problems, just like this one. In fact, due to the cruel beauty of the mathematical universe, there are infinite times as many undecidable problems as decidable problems.

Now consider problem 2. If X is equal to true, then the answer to this question is obviously yes. However, since X could be something like false, this problem is undecidable. This means that we cannot design an algorithm to solve this set of problems; even though X could be equal to true.

Could Bender Solve Any Decidable Problem?

The simple answer is yes. Bender belongs to a class of machines called UTMs ( Universal Turing Machines ). If we return to the game example, I can better explain what this means. Simply, Bender is sophisticated enough to play a game where the rules of the game are to play the rules of any other game.

This definition leads us to a somewhat surprising conclusion. If we were to build a game that simulates Bender in every single way, then Bender would be able to play it. Moreover, he could play a game that simulates himself in every possible way. But, this is no contradiction. In fact, this is what all your computers do. The web browser that you’re using to read this blog is a simulation of a machine that can solve all the same problems as the very machine on which it’s running.

Inside this game, in which Bender is our protagonist, there is a game that he can play, where he is the main character. Moreover, Bender can play a game that simulates himself playing a game that simulates himself. There is still no contradiction here. But, we can use this fact to lead us to a contradiction for our proof.

Is Fry's Question Decidable?

Fry is asking Bender a question. But, is it decidable? Could a bender be programmed to answer a question in the form “Does this bender with this input X say jump?” If not then there is no need to attempt building such a bender.

But, it’s hard to prove an algorithm doesn’t exist, if we can’t find it. So, in order to prove that it doesn’t exist, we must first assume that there is a bender who can answer this question, and then find a contradiction that shows he doesn’t exist.

This hypothetical bender will say jump, if Bender can answer Fry’s question. Let’s see if we can find a contradiction like we did with Problem 1.

Illustration 1

Shown in illustration 1 is Bender, who takes—as input—a bender(Bendito), and a question. Bender will output yep if Bendito outputs jump as his first output or bite my shiny metal ass on any other output.

But then, an evil software developer decides to change the program, ever so slightly, so that Bender will say jump if Bendito does not say jump as his first output. Keep in mind that this evil developer makes no changes to the decision making algorithm. He is only changes one of the two possible outputs of that algorithm. This new Bender, Bender1, is shown in illustration 2.

Illustration 2

Now, let's imagine that a super-evil software-developer decides to make another change to the program such that Bender only takes a single input. This new single input contains Bendito. And, after bender takes in this Bendito he feeds Bendito into himself as input. Again there are no changes made to the deciding algorithm. This new bender, Bender2, is depicted in illustration 3.

Illustration 3

Now we can find our contradiction in the design of this program, and thus show that such a bender does not exist. Let us consider scenario when Bender is fed into himself, that is we assume that Bendito is Bender. We are thinking of this as if Bender is asking himself “If I ask myself 'if I ask myself "if I am programmed to X then will I X?" then will I answer jump?' then will I answer jump?” If Bender answers yep then he is showing that he will jump. However, if he answers yep then he is showing that the Bender he fed into himself will not jump. Since Bender is Bender, he will jump and not jump, at the same time. He cannot jump and not jump at the same time↯. Therefore, we have contradicted the existence of a bender who can answer this question. And, even more, this shows that Bender1 cannot exist and therefore Bender does not exist either.

If this seems a little confusing, let's look a similar problem, in which we are programming Pinocchio's instead of benders. If we are to program Pinocchio to say, "my nose is going to grow," will his nose then grow? If his nose does not grow, then he is telling a lie and his nose will grow. If his nose then grows, he is telling the truth, so his nose does not grow. His nose will both grow and not grow at the same time↯. This is our contradiction.

Good news everyone! Bender does not exist. Well, at least a bender who could solve such a problem could not exist. This is great news though, because we no longer have to try to design such a bender. We know that he cannot exist. So, f*** it. :)

The bender described in this article is completely analogous to the Hello World program described by Hopcroft et al². When a programmer is faced with a problem that she thinks is undecidable she can write a program using the Hello World program to make the decision. If she can do this then she has shown that the problem is undecidable.

An Experiment You Can Do With Friends

As a fun experiment you can ask a friend if the next thing she will say is “no”. Write down your results. Is what she said next consistent with her answer?

References

An Undecidable Bender by Jesse Riggs is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Based on a work at jesse-riggs.com.