(I've been on vacation for the last 10 days on a
Tauck Bus Tour of Canada with Helihiking.)
What is the probability that a bus tour has on it two people that know
the proof that S2S is decidable?
(Original Proof by Rabin is
here.
For reviews of several books on the topic see
here.)

Not a trick question. The bus tour was not organized
by the Association of Symbolic Logic.

The prob seems like it would be low. But this is not the right way to look at it.

This did happen.
Suzanne Zeitman was on the tour.
I learned about the proof from her (excellent) writeup which, alas, is
not online. It is incorporated in the book
The Classical Decision Problem by Borger, Gradel, Gurevich.

Should I be saying `WOW! that is so unlikely, yet it happend!'.
No. Consider the following fictional conversation:
BILL: The most amazing thing just happened!
I just tossed a coin 40 times and got HHTTTHTHTHTHHTTTTHTHTHTTHTHHHTTHHTHTHHTH.
LANCE: Why is that remarkable?
BILL: Because the prob of that particular sequence is so small!

The prob that someone the distance away from me which Suzanne Zeitman
is (I have written some math reviews for her and been in
some email contact)
happens to be on the same bus trip as me may be
low, but its not so low as to be astonished if it happens.
This is my third bus trip and the
first time it happened. Is the probably 1/3? I doubt that, but
its not so low as to be notable.

If before going on the trip I had said Gee, I wonder is someone who knows
the proof that S2S is decidable will be on the tour? then THAT Would
be notable.

What is the prob that the maintainer of the
ErdosNumber Website was, Jerry Grossman,
was on the trip? This is a trick question Jerry Grossman is Suzanne
Zeitman's husband.

What is the prob that on the trip there were
people who know, through their homeowners association,
Steven Simpson
an eminent logician who works on Reverse Mathematics, who I know.
This did happen. Not a trick question, but again, not that notable.
In response to point #4, the real question is: what is the probability that something would happen on your bus trip that you would find interesting enough to post about on your blog.
ReplyDeleteWhat is the probability that the wealthiest, most technologically advanced nation in the world in 2008 will not broadcast one single Olympics event LIVE on TV? That's right, not even one in the west coast. To add insult to injury, they put the word "LIVE" on the screen when in fact it's a 3hour delay. Do they really think that the average American IQ is that low? I guess so. Sorry for being slightly offtopic.
ReplyDeleteThe "bible code" claim runs along somewhat similar lines.
ReplyDeleteSee
www.ma.huji.ac.il/~kalai/bc.htm
to anon #2: no, they only think the average IQ of west coast Americans is that low...
ReplyDeleteALL of the Olympic broadcasts WERE live, unless you were watching a repeat airing.
ReplyDeleteBoth the east coast AND west coast feeds were shown at the exact same time. I know this because I have a satellite dish on which I could see the New York broadcast as well as the Los Angeles broadcast at the exact same time, and they were broadcasting the exact same thing.