The Liar Game: Truths & Proofs from Euclid to Turing

speaker: Dr Mark Wildon venue: The National Library date: [2017-12-14 Thu 18:30:00]

https://www.youtube.com/watch?v=UYffm5P29Co

Euclid to Turing, the search for truth connects them infinitely many primes

• Euclid’s proof via the Socratic method

Guess a number from 1 to 15

• a binary tree with 15 leaves have depth 4
• left or right down the tree give us the binary code for the number

Reliable communication in the face of errors

• redundancy in the message, repeat each bit 3 times
• how many questions to guess 0 to 15 if the person is allowed to lie once
• Hamming invented a one-error correcting binary code of length 7 with 16 codewords
  • so that the computer can read his punch cards correctly
• no strategy can use fewer than 7 guesses, Hamming’s code is optimal

Ada Lovelace insight that computers could do many different things

• Turing proved that there is no algorithm to decide the truth or falsity of a mathematical statement