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.