(
20th Maryland TCS Day
Tue, Oct 14, 2008 9:30am - 4pm)
The
liar paradox
is very
similar to the serious math of Godel's Incompleteness theorem.
Berry's Paradox
is very simlar to the serious math of the Kolmogorov function
(map x to the length of the shortest description of x)
being noncomputable.
Is their any serious math that is similar to the
Unexpected Hanging Paradox?
Here is the paradox:
A judge tells a condemned man that he will hang on
either M, Tu, W, Th, or Friday at 1:00PM
And that he will be surprised when it happens.
His lawyer tells him not to worry: The hanging can't happen
on Friday, since if he is alive by Thursday at 1:01PM
then he knows it will be on Friday and hence won't be surprised.
However, he also knows he can't be hung on Thursday since
Friday is out, so if by Wedensday at 1:01PM he alive he will KNOW that
it is Thursday. Hence he won't be surprised. Hence it can't be Thursday.
Proceeding like this he reasons that he can't be hung.
On Thursday the judge comes with the noose- and the prisoner is
surprised.
I'm not asking for a resolution-- it seems to be a
significant problem for philosophy--
however, I am asking: Is there some serious math that is similar
to this paradox?
It's just Gödel's theorem! "I will hang you tomorrow. You can not consistently prove that I will hang you tomorrow." is pretty much the same as "Bill Gasarch cannot prove that this sentence is true." or "This sentence has no proof in ZFC."
ReplyDeleteThe unexpected hanging paradox wikipedia page links to Centipede game, which does seem to qualify as serious math. A's optimal strategy can't pass in the last round, so B's optimal strategy can't pass in the 2nd-to-last round, and so on.
ReplyDeleteI'd be curious to hear people's resolution of the paradox.
ReplyDeleteFor me, I think it boils down to the fact that "surprise" is ill-defined, and any attempts to formally define it either make the initial statement obviously false or obviously true.
My take: You have to take into account the possibility that the judge lies and the prisoner is not hung. In fact this is the conclusion of the lawyer.
ReplyDeleteNow the lawyer's logic can't be applied since not being hung on Friday simply means the judge lied. And everything the judge said was true: The prisoner was hung and surprised when it happened.
Isn't it clear? Having made such a claim, the judge is obviously irrational and thus cannot be involved in iterated reasoning about knowledge.
ReplyDeleteI think an essential difference of this question with the other two you mentioned is its use of subjective knowledge, not language. Therefore, I think the curious math problem will probably come from game theory, AI, ... or something like that.
ReplyDeleteFor the paradox, it is completely obvious that the prisoner reasoning is not correct. The first step in the argument is problematic, because he assumes that he will be killed tomorrow, and then argues that he will know that (which is not true), so he will not be killed tomorrow.
Isn't the induction just a distraction? You don't need it. The judge tells you you'll be killed this week, and it will be a surprise. You deduce it can't be on Friday. The judge has you killed on friday, and its a surprise.
ReplyDeleteIts a paradox because "surprise" is not defined. If the judge tells you you'll be killed in one of 5 days, then how can you be surprised when its anyone of them?
ReplyDeleteDo you mean surprised relative to the choice of days? Even that's not well defined: you can have a 20% expectation of getting killed on the first day. If it doesn't happen, then you can have a 25% expectation on the second day etc. What is the threshold for surprise?
as someone else mentioned, the literature on repeated games uses this line of reasoning quite often. a canonical example is repeated prisoner's dilemma.
ReplyDeleteUsually in mathematics we are surprised and gratified when unexpected mathematical structure is unveiled.
ReplyDeleteBut sometimes this expectation is frustrated, and this frustration can be viewed as the common element in the liar paradox, the Berry paradox, and the hanging paradox, in the sense that these paradoxes point to the (unexpected) absence of (computable) structure.
So another way to phrase this question is, what are some examples of mathematical proofs that seem counter-intuitive because they demonstrate that an expected mathematical structure is in fact nonexistent and/or noncomputable?
At mathematically simple level, one familiar example is the paradox of the gambler's ruin: we expect to be able to exploit "runs of luck" at the roulette table, but in fact no such strategy exists.
These issues arise frequently in simulation theory, which (broadly conceived) includes attempts to predict the behavior of "the hanging judge."
It's kind of a quiet thread ... so I'll suggest an ancient mathematical paradox that (arguably) parallels the Unexpected Hanging, namely, Zeno's Paradox.
ReplyDeleteThe parallel with the Unexpected Hanging Paradox is simply this: in Zeno's Paradox, the tortoise was surprised when Achilles passed him.
Are there any similar surprises in modern-day mathematics? Surely. One surprise that broadly impacts us engineers is the surprising amenability of many large-scale systems (both classical and quantum) to efficient simulation.
For example, our present mathematical understanding of density functional theory (DFT) is roughly on a par with Zeno's understanding of limits and continua. We know that DFT works well, but we don't understand why in any satisfyingly fundamental way.
From this point of view, paradoxical surprises sometimes indicate that the starting postulates of a mathematical discipline need to be clarified and deepened.
Let me point out that Timothy Chow (recent inventor of almost-natural proofs) wrote a survey paper on the paradox that was published in Amer. Math. Monthly. So arguably, the paradox itself qualifies as serious math.
ReplyDeletePeter, thank you for that fine link to Timothy Y. Chow's outstanding article.
ReplyDeleteA long time ago, Yoram Moses
ReplyDeleteand I wrote an article on this
(see http://www.cs.cornell.edu/Info/People/halpern/papers/surprise-test.pdf). We provided three translation of the puzzle into a mathematical formalism. Roughly speaking, the idea was that the judge is telling you that you won't be able to prove, from what he tells you, at 9 AM on the day you'll be hanged, that you will hang that day. In the first translation, you deduce an inconsistency, and every single day you and prove that you will hang that day (so you're not suprised when you do). In the second, you can' ptove anything.
The third translation is the most mathematically interesting, since it involves self-reference in a serious way. It is true iff it is false. Bottom line: I think there is some serious math here, and it involves giving truth values to self-referential sentences. It's thus related to, but different from, Godel's proof and other paradoxes involving self-reference.
As with all things, the problem is resolved by "expectation of death".
ReplyDelete(Meta-physicians live for week-ends.)
-t
I don't think it's a mathematical problem, for the following reason:
ReplyDeleteThe judge states that the prisoner will be surprised. Surprise entails not knowing an outcome ahead of time. The judge is saying, in effect, that he or she knows that the prisoner will NOT know the outcome, at the time. So the judge knows what the prisoner will be thinking in the future! Hence the judge is claiming clairvoyant and telepathic powers!
Well, you might say that the prisoner is a logician (or listens to his logician lawyer), so he will definitely know that he can't be executed. Why? Because the impossibility of execution is provable (the puzzle provides the proof). Hence the judge need not be clairvoyant. "The truth is out there", and all we need to do is discover it through proof.
But I feel that a proof is an article of persuasion, not an absolute. Aren't proofs artifacts of the human mind, which has its own idiosyncratic ways? Can't we conceive of aliens who might think differently? Someone may persuade herself of some idea, and yet change her mind.
Alejo
I've come up with my own solution which is not on wikipedia. Forgive me if it's already been mentioned here. Firstly the statement is not contradictory. Second here are the assumptions I'm using: The judge means that (1) "The prisoner will be executed next week on a weekday and the date will not be deducible using this statement.",(2) the prisoner knows the judges statement to be true and will know it to be true all of next week. The judges statement is not a paradox. The paradox lies with the prisoner's argument. The prisoners first point is that if he survives until Thursday he will know the date of his execution is Friday based on axiom 1. However, if he can deduce the date from axiom 1 then axiom 1 contradicts itself because it states that he cannot deduce the date. Therefore the rest of his argument is false. So, the judges statement is true but the prisoners argument is false because it is contradictory for axiom 1 to be true and him to survive until thursday.
ReplyDeleteSeems to me the judge is counting on the prisoner using the logic stated in the problem and assuming he would not be hanged on Thursday. Since he was hanged on Thursday the prisoner is surprised by the hanging because he had concluded he would not be hanged on Thursday. The judge was making a prediction of the surprise by assuming the prisoner would use false reasoning about his chances of being hung on a patricular day.
ReplyDeleteWe have an induction, so the conclusion is going to be determined by the base case, i.e., what happens at 1pm on Friday, the final day. Specify that and everything else becomes clear.
ReplyDeleteThere are two variables: what the prisoner knows/expects and whether he is hanged or not.
If the prisoner *must* be hanged, then the prisoner will know it is going to happen when 1pm on Friday rolls around. Does he get hanged? This is the base case.
If he gets hanged at 1pm on Friday then the premise that it can't happen if the prisoner knows/expects it to happen is violated. If he is set free then the premise that he must be hanged is violated. The paradox is then revealed to be an obvious contradiction of premises which renders our base case undefined.
(Note that if the judge tosses a coin or simply frees the prisoner on Friday then the induction also breaks down because on each day the prisoner has no way of knowing whether he will ultimately be hanged.)
I believe that the paradox does not exist for any day except the last day, Friday. On Friday morning, the prisoner deduces for certain that he must be hung that day but he can't be hung that day as per the judge's decree. If the prisoner is hung or not hung, the judge's decree, as stated, is not being carried out. This failure only applies to one day, Friday!
ReplyDeleteTo erroneously pick up the earlier days, the prisoner engages in a REVERSE Mathematical Inductive Process in the future. He jumps to a FUTURE time, Thursday at noon of the following week. Shortly after noon that day, he becomes aware that Thursday is not going to be the day of the hanging. He knows the Friday can't be the day either as deduced correctly above. Now he attempts to apply Mathematical induction on the other days.
Mathematical induction is proven to work when you make a deduction that works for the test case and then proceed forward in a falling dominoes manner picking up all future cases. From this point, on a future Thursday, if he deduced events which will occur AFTER that Thursday, he would be okay and the inductive process would produce correct results.
However, in this case, he stays in the future and runs his inductive process back towards present time! Reverse induction works once in a while but in the general case it does not always work. As the prisoner runs his inductive process backwards towards present time, the information which he obtained on various later days is no longer with him. In particular, he moves backward before the Thursday, a week or so in the future, where he learned that the judges decree would fail on Friday. That knowledge which occurred just after noon was not known in the time period in which the inductive process is run backwords. The decision that Friday is eliminated is not yet known in those earlier days and yet THIS AS YET UNKNOWN DATA IS STILL BEING APPLIED AS IT IS KNOWN. The reverse inductive process must fail as it assumes a not yet known fact to be true.