(I've been on vacation for the last 10 days on a
Tauck Bus Tour of Canada with Heli-hiking
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
For reviews of several books on the topic see
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
What is the prob that the maintainer of the
Erdos-Number Website was, Jerry Grossman,
was on the trip? This is a trick question-- Jerry Grossman is Suzanne
What is the prob that on the trip there were
people who know, through their homeowners association,
an eminent logician who works on Reverse Mathematics, who I know.
This did happen. Not a trick question, but again, not that notable.
Posted By GASARCH to Computational Complexity at 8/11/2008 11:30:00 AM