Alan Turing, Computing, Bletchley, and Mathematics

2015-07-01 1830 speaker: Rod Downey, Victoria University, Wellington event: IMS Public Lecture

** Turing award awarded by the ACM ** Propositional logic is complete a tautology can be established by the tableau method ** Checking if there exists an assignment that make a statement true is hard satisfiablity problem ** Predicate logic Propositional logic is too simple, add predicates, and quantifiers ** Hilbert ask if there is a decision procedure for predicate logic similar to the tableau method for propositional logic ** To show no such procedure exists, it is necessary to have a model of a “decision procedure” Church proposed lambda definablity, Turing proposed Turing machine ** Turing Machine Building a yellow brick road example ** Partial recursive functions not convincing ** Turing argues that his machines formalizes a human computer ** Notion of a universal machine machine can be made generic! logic can be in the program ** Turing learned of mechanical computers from Tommy Flowers’ work on the Colossus machine ** Turing proposed ACE, never built. Huxley’s G15 is bsaed on ACE

** Bayesian statistics were use for attacks and planning at Bletchley ** Timeline of Enigma 1925 Enigma machine patented in London 1926 Edward Travis, deputy director, goes to Berlin and buys one from the manufaturer Used in the Spanish Civil war German military modified the Enigma Polish invented the Bombe 1939 Polish gives two current Enigma to British, and a

• hidden message that they recruited mathematicians to become cryptanalysts Turing requests to tackle the Naval Enigma Germans had absolute faith in the unbreakablity of Enigma ** Breaking Enigma work of 10k people, broken because of operator errors, chance discoveries. Data mining! Hut 6 breaks Airforce Engima using the Herival Tip a flaw of the Enigma is no letter is encrypted to itself

** Turing proposed symbolic verification of programs leading to model checking ** Unpublished paper on this from a sabbatical at Cambridge His boss, Charles Darwin, would not let it be published ** Morphogensis: how do leopards get their spots His theory was later experimentally verified

** Connection to Babbage Turing probably new of the work, but was not influenced by it (probably).

** What made Turing so successful? He is quick to learn, and get to the frontier. Eg Terry Tao Think in terms of the basics.