Comments on Computational Complexity: The Unexpected Hanging Paradox-any seriosu math th...

I don't think it's a mathematical problem, for the...

2008-10-18T16:03:00.000-05:00

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

As with all things, the problem is resolved by "ex...

2008-10-15T03:07:00.000-05:00

As with all things, the problem is resolved by "expectation of death".

(Meta-physicians live for week-ends.)

-t

A long time ago, Yoram Mosesand I wrote an article...

2008-10-11T21:41:00.000-05:00

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.

Peter, thank you for that fine link to Timothy Y. ...

2008-10-11T11:57:00.000-05:00

Peter, thank you for that fine link to Timothy Y. Chow's outstanding article.

Let me point out that Timothy Chow (recent invento...

2008-10-10T01:56:00.000-05:00

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.

It's kind of a quiet thread ... so I'll suggest an...

2008-10-08T05:44:00.000-05:00

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.

Usually in mathematics we are surprised and gratif...

2008-10-07T06:48:00.000-05:00

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."

as someone else mentioned, the literature on repea...

2008-10-06T19:13:00.000-05:00

as someone else mentioned, the literature on repeated games uses this line of reasoning quite often. a canonical example is repeated prisoner's dilemma.

Its a paradox because "surprise" is not defined. ...

2008-10-06T18:45:00.000-05:00

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?

Isn't the induction just a distraction? You don't ...

2008-10-06T18:06:00.000-05:00

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.

I think an essential difference of this question w...

2008-10-06T18:04:00.000-05:00

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 it clear? Having made such a claim, the judg...

2008-10-06T15:15:00.000-05:00

Isn't it clear? Having made such a claim, the judge is obviously irrational and thus cannot be involved in iterated reasoning about knowledge.

My take: You have to take into account the possibi...

2008-10-06T15:04:00.000-05:00

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.

I'd be curious to hear people's resolution of the ...

2008-10-06T12:29:00.000-05:00

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.

The unexpected hanging paradox wikipedia page link...

2008-10-06T10:49:00.000-05:00

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.

It's just Gödel's theorem! "I will hang you tomor...

2008-10-06T10:21:00.000-05:00

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."