I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:
You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:
Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?
In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general
The answer to Hilbert’s Tenth Problem problem is
No such algorithm exists.
This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.
I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.
Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?
The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.
I welcome you to think of a number and write the corresponding yes/no questions as a comment below.