There was a *really great* adventure-game puzzle built around these
printers.

Ever since waking up, I've been trying to figure out what that terrific puzzle was. I know it had to do with paradoxes. You know, like the Liar: "This sentence is false."

(By the way, I'm going to slap the next person who says "I am a Cretan. All Cretans are liars." Because that's not a paradox. That's just a pair of lies. It was uttered by Anatoles, the Notoriously Dishonest Personage of Thebes, and he was slandering Crete outrageously; Cretans are no more untrustworthy than anyone else. Well, anyone else except Syracusians. But that's another paradox.)

Now, it's easy enough to write some Inform code (or TADS, I assume, but I know Inform) to parse sentences like "The red pyramid is on the green cube", and determine truth or falsity. You know, the old SHRDLU dialogue. Whip up a short grammar of statements ("OBJ is [not] on OBJ", "OBJ is [not] under OBJ", "OBJ is [not] touching OBJ", "OBJ is [not] PROPERTY"), create appropriate Inform objects, and the truth-tester routine is a few minutes' work. (Life gets harder if you allow compound statements -- "and", "or" -- so we won't.)

None of this is any fun unless we can write statements which refer to the truth or falsity of sentences. How do we sneak that in? "This sentence is false" is a bit of a nuisance to parse in Inform, since "this" is a pronoun. Two different pieces of paper could say "This sentence..." and they would not be referring to the same object. And how would you refer to "that sentence"? "The sentence on the wide paper is false"? (Long paper, short paper, wide paper, torn paper...) Way too much typing, though.

Let's go with that colored-printer idea! You write a sentence on a piece of paper, and stick it in the printer. The paper turns green if the sentence is true, or red if it's false. So you take your long piece of paper and you write "The red pyramid is on the cube", and then you take your wide paper and write "The long paper is red". Now we're using the same parsing routines and the same statements as before -- always a win. The truth-tester routine acquires one special case, which calls itself recursively. No problem.

Well, it *is* a problem, as soon as you try the interesting case:
when the short paper says "The short paper is red." Now your recursive case
loops forever. But really, you want to special-case that as well. Actually,
we'll need a little more cleverness, to take care of multi-step loops. ("The
short paper is red." "The long paper is green.") We need an array to track
this chain and see whether it loops back on itself, or bottoms out with an
"ordinary" factual statement. Fortunately, we already decided to disallow
"and" and "or", so it's just a chain, not a tree... and as long as we limit
the number of paper slips, we can limit the maximum size of the chain.

I didn't feel like inventing more than four adjectives for "paper" anyhow.

So we detect a loop, and, conveniently, there are just two possibilities. It can boil down to "This sentence is false," or "This sentence is true." The former can't be either red or green. The latter can be either.

So how does our Inform object react to the Liar? Make it turn grey, I figure. A nasty static-colored grey. Snow-crashed paper. Cool!

Hey, as long as we're inventing new colors, what about "This sentence is
true"? That should turn a *fourth* color, say brown, a muddy
combination of red and green...

The point of a fourth color is to represent (not just *symbolize*)
the logical state of a statement which can consistently be either true or
false. We'd better make it *ripply*, a color in which green and red
are both visible. Of this paper, we can safely say both "It is red"
*and* "It is green". Easier to describe than to visualize, but this
is why I'm in text games.

Of course, the player might still write (on the short paper) "The short
paper is ripply." We'd like this to model the statement "This sentence can
consistently be either true or false." Is it? (Oh, dear, the conjunctions
have snuck up on us.) Well, if it's true, then it *can* consistently
be either true or false. If it's false, then it must either be definitely
true, definitely false, or inconsistent in either state. Let's see... The
statement is certainly consistent if it's false. If it's true... well, that
could go either way! If it's consistent when it's true, then it can
consistently be either true or false, which demonstrates that it's
consistent if it's true. And if it can only be consistent when it's false,
then it *can't* be consistent in both states, which makes it false.
This piece of paper can be either ripply or red! We'll need a new color...

"The short paper is grey" runs into a similar problem. That should mean "This sentence cannot be consistently be either true or false." Headaches ensue.

You know, this four-valued logic really isn't working out very well. Perhaps we should go back to a naive view of color. "The short paper is grey" turns red because, well, red means false, and a red piece of paper is not grey. "The short paper is brown" turns red too.

Really, I think I've been engaged in a certain amount of verbal kerfuffling. The usual notion of "logical proof" -- analyzing whether a statement is true or false -- relies on proof by contradiction. You assume a value for a statement, derive a contradiction, and thereby prove the opposite value. But if "contradictory" is just another value, the structure gets rather shaky.

(Shall we write "Grass is grey" on our piece of paper? Now if grass
*isn't* grey -- and it isn't -- this paper should be grass-green. But
if grass *is* grey, we can look out the window, observe that it
isn't, and thus arrive at an inconsistency. So the paper can be either grey
or green... yet another color... no, wait, that's not right...)

Is the law of the excluded middle so important? As it turns out -- yes. Did
you ever wonder *why* all those logic puzzles are set on the Island
of Knights and Knaves? Because the puzzle-setter has to specify that every
statement in the puzzle is *either true or false*! If he doesn't tell
you *that*, then you can't logically deduce anything at all... Which
is why a human being can pronounce the words "This sentence is false"
without his lips catching fire.

Re-read that; it's important. A logic puzzle can give you a random
statement, even a self-referential one, and ask you "Was this spoken by a
knight or a knave?" That's a well-founded question. The unspoken assumption
of the puzzle is that it's one of the two. *Given that assumption*,
you may be able to prove the speaker is a knight; you may be able to prove
the speaker is a knave; you might not be able to prove either; or you might
be able to derive a contradiction, *thus disproving the assumptions of
the puzzle*. The only explanation *then* is that the
puzzle-setting has lied to you. (Of course, the Island of Knights and Knaves
is fictional, and are not all fictions basically lies? But I digress.)

No wonder we're having so much trouble with our damn pieces of paper. We're
not just trying to model truth and falsity -- any Liar can do *that*
-- but provability and unprovability. Green means "If you, an arbitrary
personage on the Island of Knights and Knaves, say the sentence here
inscribed, then I can prove you are a knight." Red means "If you say this
sentence, then I can prove you are a knave." Brown means "...I cannot prove
either," and grey means "If you say the sentence written here, I can prove
you are not from the Island of Knights and Knaves!"

Dear, dear me. If a fellow from the Island walked up to me and says "You
cannot prove whether I am a knight or a knave," I would really have no idea
how to proceed. (And then *you* could observe that the fellow's
statement is true, and therefore he must be a knight. But *I*
couldn't make that deduction! You are clearly smarter than me!)

...As you see, the role of the logician in this puzzles cannot simply be
waved away. We have to decide in advance *what "provable" means*, in
order to know what colors our papers should turn.

A Stupid Logician can observe objects (and their colors, shapes, etc). He
can also work out the logical consequences of statements. But he won't claim
he can *prove* these conclusions. It's a blind spot; he is ignorant
of how his own mind comes to conclusions.

So if you show a Stupid Logician a blue sphere, and ask him if it's red,
he'll say "No." If you tell him you have a cube, different in color from the
sphere, and then you ask him if the cube is blue, he'll say "No." In fact,
he *has* proved the answer is "No", by considering the information at
hand. But if you *ask* him "Can you prove the sphere is not red? Can
you prove the cube is not blue?" he'll answer "No, and no."

(What? You just said the sphere wasn't red, and the cube wasn't blue!)

"Well, I know. I certainly hold those opinions. But I can't imagine how to
*prove* them. They just seem obviously true!"

(But you did just prove them, in your head!)

"I'm sorry, I get all confused when I try to think about my own head. I've given up trying."

Perhaps I should have named this humble reasoner the "Taoist Logician" instead. Ah, well, too late.

Now it becomes quite easy to rigorously describe our colored pieces of paper. You write a sentence on the paper. If the sentence -- presumed to be either true or false -- can be recognized as true by a Stupid Logician, then the paper will turn green. If it can be recognized as false, we get red. If the Stupid Logician cannot deduce anything about the sentence, we get brown; and if a Logician deduces that the sentence cannot be spoken by an inhabitant of the Island of Knights and Knaves, we get grey.

And where does this get us? Not far into the land of paradox, unfortunately.

You can write "This paper is red." What color does it turn? We have defined
that the paper will turn red if, when an Islander recites its statement, a
Stupid Logician can deduce that the Islander is a knave. In this case, "its
statement" is that very assertion -- that a Stupid Logician can recognize
that the statement is false. *Can* a Stupid Logician deduce that he
himself can prove the statement false? Of course not! A Stupid Logician
doesn't think he can prove *any* statement true (or false). Only a
knave would say he could. And so the paper turns red.

(Note that our description of the paper does not require the Stupid Logician
to *observe* the paper -- even in this self-referential case. If he
*did* observe its redness, he would become most confused... with good
reason. Here is paper which is very obviously red, but by the definition of
the paper's mechanism, if an Islander says it is red, our Stupid Logician
friend should deduce that the Islander is a knave, not a knight... I think
this simply proves that a Stupid Logician can never observe the piece of
paper in question! Just as an Islander can never say "I am a knave." It's a
violation of the conditions we have undertaken for our speculation.)

Of course, if you changed the sentence to "This paper is green," the paper
would turn red just the same. If you wrote "This paper is brown," it would
turn green (since a Stupid Logician really *can't* deduce anything
about the statement). If you wrote "This paper is grey", it turns... worked
it out? Red. (Because our paper turns grey if a Stupid Logician deduces that
neither a knight nor a knave can recite its statement; and again, a Stupid
Logician doesn't think he can deduce *anything*.)

This fine specimen can deduce everything that his Stupid cousin can -- he
can observe objects and draw conclusions. He can also *prove* that he
can observe objects and draw conclusions. He knows the sky is blue, and also
*knows* that he knows it. However, this introspective faculty does
not extend to knowing that he knows that he knows the sky is blue. He cannot
recognize that he has this ability to deduce observations and simple
conclusions.

You know, if I try to rephrase that to be less confusing, my head is going to split.

The point is, the Mostly-Stupid Logician has straightforward introspection,
but not recursive introspection. So we create a new sheaf of paper.
*This* stuff turns green if the sentence on it can be recognized as
true by a Mostly-Stupid Logician. And so on.

Does this help?

Well, no. All the interesting paradoxical statements *are* recursive.
The Mostly-Stupid Logician will be just as baffled about his ability to
prove them as the Stupid Logician was.

What about the Not-So-Stupid Logician? He can recognize that he can
recognize true statements -- and he can recognize that he can can recognize
that he can can recognize them -- and so on, to any *finite* number
of steps. He is recursive, just not self-referential.

This still doesn't help, however, because the paradoxes we're talking about are the self-referential ones.

Let's make some Clever Logician Paper. It turns green if the sentence on it can be recognized as true by a Clever Logician. It turns red if the sentence on it can be recognized as false by a Clever Logician. And so on.

"This paper is red." Equivalently, "This sentence (presumed to be either
true or false) can be proved false by a Clever Logician." The Clever
Logician hypothesizes that it's true, so it can be proved false, and all
Logicians are consistent, so it is false... contradiction... so it is proved
false... but it *says* it can be proved false, so it's true...
contradiction...

Well, that's the Liar all right. No help there.

A *straightforward* paradox? Ah, now this is a promising approach. Of
course we can't characterize *all* paradoxical statements. That's
basically the same task as characterizing all true-but-unprovable statements
(ie, proving them!) But for a dumb little model that can fit into a text
adventure, we should be able to characterize one basic kind of paradox --
the Liar -- and be able to distinguish it as a special case.

A Slightly Clever Logician can deduce everything a Not-So-Stupid Logician can. He can also recognize the statement "A Slightly Clever Logician can prove this statement is true." He doesn't recognize it as true or as false. Rather, he knows that it could be either. (Someone from the Island of Knights and Knaves could say it, but he would not know whether the Islander was a knight.)

(The consequences of this statement are a bit odd, but still consistent. If
the statement is false, it implies that the Slightly Clever Logician can't
prove it true -- that's only to be expected. If the statement is true, then
he *can* prove it true. But he doesn't *unconditionally*
believe he can prove it! He only knows that he *could* prove it
*if* it were true.)

Similarly, he can recognize the statement "A Slightly Clever Logician can
prove this statement is false." And he knows that this statement is neither
true nor false. That is, if you told him that an inhabitant of the Island
spoke those words, he would conclude that *you* were lying.

Back to our sample paradox: "This paper is red." Equivalently, "This
sentence can be proved false by a Slightly Clever Logician." Excellent! Our
Slightly Clever Logician recognizes that this cannot be either true or
false; so the paper turns grey. *Finally.* And "This paper is green"
turns brown.

This is hardly an elegant solution. As I said, we're treating these two cases specially. All other paradoxes remain outside the Slightly Clever Logician's intuitive grasp. For example, if you write "This paper is grey," the paper will turn red -- just as the Stupid Logician Paper did. "This paper is brown" will turn green.

But the two simplest cases (the Liar and the Truth-Teller) are the ones most likely to be encountered in a logic puzzle. If you want to characterize a more general class of paradoxes, feel free!

And if we have the pair: "The next sentence is false," "The previous sentence is false," then both should turn brown. The same goes for "The next sentence is true," "The previous sentence is true."

More generally: if we have a loop of sentences, where each says the next is true or false (the last referring to the first), then this set is equivalent to "This sentence is false" if the number of "false" claims is odd. Otherwise it's equivalent to "This sentence is true."

Note that if any of the sentences claim that another (or itself) is
paradoxical or unprovable (grey or brown), all bets are off. The Slightly
Clever Logician's oracular paradox-recognizer does not handle such loops. So
all the papers in the loop will turn red -- except for those that claim that
another paper is brown. *Those* will turn green. (Because, the
Slightly Clever Logician can't prove anything about *any* of the
statements in the loop. Which is just what "brown" claims.)

The same goes for most sentences *about* a loop -- even a
recognized loop. Sentences about sentences about paradoxes are not
recognizable. Except... a few of those *are*
recognizable. Specifically: "The sentence 'this sentence is false' is
false." This seems to be about the Liar, but it's actually
*identical* to the Liar! It's worded differently, but it makes
the same claim that the Liar does. The Slightly Clever Logician
notices this. The same goes for "The sentence 'this sentence is true'
is true," and other rewordings of recognized loops.

I'm not sure.

I've created a text adventure sample game that implements Slightly Clever Logician Paper. It works; it gets the answers I've described. But playing around, stacking cubes and pyramids, and even writing down the Liar paradox, doesn't make all that exciting a game.

So I'm opening up the floor to submissions. As of February 2003, I'm running a Mini-Competition on the theme of logic puzzles. My sample Inform code is available; you can use it or not.

(This essay is copyright 2003 by Andrew Plotkin.)

Last updated February 10, 2003.