Logic and Games

Hi All,
Well, it has been some time since I have posted anything technical on this blog. Lately I have been very lazy about writing down interesting things over here. The biggest pain that I face is that there is no support for latex in blogspot.

Anyways, coming down to the point. I am attending a few lectures by Rohit Parikh at Logic School. He is a very good orator, I must say. As a part of his talk on "Finite and Infinite Dialogues", he mentioned a very famous product-sum puzzle. I am writing it down here just for the sake of completeness.

----

Mr P and Mr S are told product and sum of two number a and b respectively, where 2<= a,b <= 99.
P : I don't know the numbers.
S : I knew you did not know them.
P : Now, I know the numbers
S : Now, I know them too.

the solution can be found from dijkstra's paper.
----

With this example, Prof. Rohit went on to describe interesting world of finite and infinite dialogs between two parties in order to determine certain information. Yet another interesting example that he gave was as follows :

A randomly chosen positive integer n is chosen. One of them is written on Ann's forehead and n+1 is written on Bob's forehead. Now, each of them are asked to determine the numbers written on their forehead.

If 1 is written on Ann ( called as A now on ) and 2 is written on Bob ( called as B from now on ). Bob can immediately deduce that his number is 2. If A has got 3 and Bob has got 2 then A have two possibilities 1 or 3. When Bob says I don't know, A can determine that number she has got is 3. It is easy to prove by induction how they can determine their numbers in linear time with respect to number n.

One can devise a game where it would take infinite amount of time to determine one's number. Here is the interesting lecture notes which covered these beautiful examples.

PS : Please note that lecture notes/papers may be copyrighted. Contact the authors in case one wish to use it for non-academic purpose.