Oxford University Press's
Academic Insights for the Thinking World

Paradox and flowcharts

The Liar paradox — a paradox that has been debated for hundreds of years — arises when we consider the following declarative sentence:

“This sentence is false.”

Given some initially intuitive platitudes about truth, the Liar sentence is true if and only if it is false. Thus, the Liar sentence can’t be true, and can’t be false, violating out intuition that all declarative sentences are either true or false (and not both).

There are many variants of the Liar paradox. For example, we can formulate relatively straightforward examples of interrogative Liar paradoxes, such as the following Liar question:

“Is the answer to this question ‘no’?”

If the correct answer to this question is “yes”, then the correct answer to the question is “no”, and vice versa. Thus the Liar question is a yes-or-no question that we cannot correctly answer with either “yes” or “no”.

Interestingly, I couldn’t think of any clear examples of exclamatory variants of the Liar paradox. The closest might be something like the following Liar exclamation:

“Boo to this very exclamation!”

If one (sincerely) utters this sentence, then one is simultaneously exhibiting a positive attitude towards the Liar exclamation (via making the utterance in the first place) and a negative attitude towards the exclamation (via the content of the utterance). But I am far from sure that this leads to a genuine contradiction or absurdity.

OUPJune15Fig1
Figure 1, image courtesy of Roy T Cook. Please do not reproduce without permission

There are, however, a number of very interesting imperative versions of the Liar. The simplest is the following, popularized in the videogame Portal 2:

“New Mission: Refuse this Mission!”

Accepting the mission requires refusing the mission, and refusing the mission requires accepting it. Thus, the mission is one we cannot accept, yet cannot refuse.

Let’s consider a slightly different kind of interrogative paradox: algorithmic paradoxes. Now, an algorithm is just a set of instructions for effectively carrying out a particular procedure (often, but not always, a computation). One of the most informative and useful ways of representing algorithms is via flowcharts. But if we aren’t careful, we can formulate flowcharts that provide instructions for procedures that are impossible to implement.

Consider the flowchart in Figure 1. It has two states: the start state, where we begin, and the halt state, which indicates that we have completed the procedure in question when (if?) we reach it. Of course, not every flowchart represents a procedure that always halts. Some procedures get caught up in infinite loops, where we repeat the same set of instructions over and over without end. In particular, the fact that a flowchart contains a halt state doesn’t always guarantee that the procedure represented by the flowchart will always halt.

The start state in Figure 1 contains a question, and arrows leading from it to other (not necessarily distinct) states corresponding to each possible answer to that question. In this case the question is a yes-or-no question, and there are thus two such arrows.

So Figure 1 seems to be a perfectly good flowchart. The question to ask now, however, is this: Can we successfully carry out the instructions codified in this flowchart?

The answer is “no”.

Here’s the reasoning: Assume you start (as one should) in the start state. Now, when carrying out the first step of the procedure represented by this flowchart, you must either choose the “yes” arrow, and arrive at the halt state, or choose the “no” arrow and arrive back at the start state. Let’s consider each case in turn:

OUPJune15Fig2
Figure 2, image courtesy of Roy T Cook. Please do not reproduce without permission

If you choose the “yes” arrow and arrive at the halt state, then the procedure will halt. So the correct answer to the question in the start state is “no”, since carrying out the algorithm only took finitely many steps (in fact, only one). But then you should not have chosen the “yes” arrow in the first place, since you weren’t trapped in an infinite loop after all. So you didn’t carry out the algorithm correctly.

If you choose the “no” arrow and arrive back at the start state, then you need to ask the same question once again in order to determine which arrow you should choose next. But you are in exactly the same situation now as you were when you carried out the first step of the procedure. So if the right answer to the question was “no” at step one, it is still “no” at the step two. But then you once again end up back at the start state, and in the same situation as before, and so you should choose the “no” arrow a third time (and a fourth time, and a fifth time, … ad infinitum). So you never reach the halt state, and thus you are trapped in an infinite loop. As a result, the correct answer to the question is “yes”, and you should not have chosen the “no” arrow in the first place. So you didn’t carry out the algorithm correctly.

Thus, the Liar flowchart represents an algorithm that is impossible to correctly implement.

Like many paradoxes, once we have seen one version it is easy to construct interesting paradoxical or puzzling variants. Once such variant, closely related to the No-No Paradox (go on – look it up!), is the construction given in Figure 2, which involves two separate flowcharts.

In this case we can carry out both algorithms correctly, but never in the same way. If we choose the “yes” arrow when implementing the first flowchart, then we must choose the “no” arrow over and over again when implementing the second flowchart, and if we choose the “no” arrow (over and over again) when implementing the first flowchart then we must choose the “yes” arrow when implementing the second flowchart. So we have two identical flowcharts, but we can only correctly carry out both procedures correctly by doing one thing in one case, and something completely different in the other.

Not a full-blown paradox, perhaps, but certainly puzzling.

Featured image credit:  “Ripples”. CC0 Public Domain via Pixabay.

Recent Comments

There are currently no comments.