Logic has a rich philosophical history for understanding the limits of our reasoning. But can it also be used for computational tasks? Nick Bezhanishvili is the President of the Dutch Association for Logic and Philosophy of the Exact Sciences. His main field of research is the relationship between logic, algebra and geometry. He recently researched the application of polyhedral semantics for 3D modeling.

Logic Puzzles

A variant of the famous "Muddy Children Puzzle"
There are three children: Alex, George and Kate. Father tells them that he has 5 hats, two white and three black. He puts hats on the children. Each child sees the hats of the others, but not their own. 

• Case 1: Kate sees two white hats. Can she guess the color of her own hat? The answer is "yes". It is easy, so we skip it. 
• Case 2: Kate sees Alex wearing a white hat and George wearing a black hat. Father asks Alex "do you know the color of your hat?". Alex answers "I don't know". Can Kate guess the color of her own hat? The answer is "yes". If she had a white hat, then Alex would see two white hats and would have guessed the color of his hat (as Kate did in Case 1). But Alex says "I don't know". So the color of Kate's hat must be black. 
• Case 3: Kate sees Alex and George wearing black hats. Father asks Alex "do you know the color of your hat?" Alex answers "I don't know". After this Father asks George "do you know the color of your hat". George answers "I don't know". Now Father asks Kate the same question. Can she guess the color of her hat? The answer is "yes". Assume that Kate is wearing a white hat. Then George sees a black and white hats and using the reasoning in Case 2 he would have guessed (as Kate did) that he is wearing a black hat. But George says "I don't know". That means that Kate's hat is black. 

Here the essential part is the public announcement "I don't know", which gives Kate the missing information. 

Knight and Knaves (From Smullyan's book)
There is an island inhabited only by knights, who always tell the truth and knaves who always lie. We just landed on this island and meet two people A and B. We ask A "are you a knight?" We do not hear the answer. We then ask B "what did A say?". B says "A said that he is a knave". Can we deduce who is A and who is B? Answer: We can certainly deduce that B is a knave. But we cannot say anything about A. If A was a knight he would have said that he is a knight. If A was a knave, he would have again said that he is a knight. Thus, in all cases A says that he is a knight. So B lied and B must be a knave.

More about Goedel and Einstein

The article "Trans-Siberian Railway" includes a chapter from Nick Bezhanishvili's recent unpublished (popular science for children) book, "Logical Adventures". The chapter concerns Goedel and Einstein, a topic discussed in the interview.

Link to the article:  https://talkthatscience.com/Trans-Siberian-Railway

Corrections of the Show

Errata 1: Goedel was not Jewish. His father was Catholic and his mother was Protestant. Goedel and his siblings were raised as Protestants.
Errata 2: Goedel did take the Trans-Siberian Railway via Russia. But then eventually sailed from Japan to San Francisco.


The tracks played during the episode:

1. Some Kind of Game, by Against all Logic
2. The Logic Song, by Supertramp
3. Logic, by Logic System

Big thanks to the Echobox Radio team for hosting us and helping out with everything!