This work is licensed under a
Creative Commons License.
|
Monday, October 06, 2008
The Unexpected Hanging Paradox-any seriosu math their?
Posted by GASARCH
(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?10:06 AM
# 16 comments
-
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."
-
The 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.
-
I'd be curious to hear people's resolution of the paradox.
For 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.
Now 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.
-
I 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.
For 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.
-
Its 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?
Do 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.
-
Usually in mathematics we are surprised and gratified when unexpected mathematical structure is unveiled.
But 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.
The 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.
-
Peter, thank you for that fine link to Timothy Y. Chow's outstanding article.
-
A long time ago, Yoram Moses
and 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".
(Meta-physicians live for week-ends.)
-t
-
I don't think it's a mathematical problem, for the following reason:
The 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
Links to this post:
Weblog Home
Archives
