Asymptotic conditional probabilities for first-order logic
Adam J. Grove, Joseph Y. Halpern, et al.
STOC 1992
A teacher announced to his pupils that on exactly one of the days of the following school week (Monday through Friday) he would give them a test. But it would be a surprise test; on the evening before the test they would not know that the test would take place the next day. One of the brighter students in the class then argued that the teacher could never give them the test. "It can't be Friday," she said, "since in that case we'll expect it on Thurday evening. But then it can't be Thursday, since having already eliminated Friday we'll know Wednesday evening that it has to be Thursday. And by similar reasoning we can also eliminate Wednesday, Tuesday, and Monday. So there can't be a test!" The students were somewhat baffled by the situation. The teacher was well-known to be truthful, so if he said there would be a test, then it was safe to assume that there would be one. On the other hand, he also said that the test would be a surprise. But it seemed that whenever he gave the test, it wouldn't be a surprise. Well, the teacher gave the test on Tuesday, and, sure enough, the students were surprised. © 1986 D. Reidel Publishing Company.
Adam J. Grove, Joseph Y. Halpern, et al.
STOC 1992
Ronald Fagin, Joseph Y. Halpern, et al.
Journal of the ACM
Joseph Y. Halpern, Ichiro Suzuki
Distributed Computing
Joseph Y. Halpern, Lenore D. Zuck
Journal of the ACM