# 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

“I'm a bender, I bend girders, that's all I'm programmed to do.” **—Bender**

### 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.

**Fry:** We can get out of here if you just bend the bars.

**Bender:** Dream on skin tube. I'm only programmed to bend for construction purposes. What do I look like? A de-bender?

**Fry:** Who cares what you're programmed for. If someone programmed you to jump off a bridge, would you?

**Bender:** I'll have to check my program... yep.

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

**Problem 1.**

*This statement is false.*

*Is the above statement true?*

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.

**Problem 2.**

*This statement is X.*

*Is the above statement true?*

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?

"When mathematicians think about algorithms, it is usually from the God's-eye perspective. They are interested in proving, for instance, that there is some algorithm with some interesting property, or that there is no such algorithm, and in order to prove such things you needn't actually locate the algorithm you are talking about..." **—Daniel Dennett ^{1 }**

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^{2}. 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.