6.042/18.062] Mathematics for Computer Science February 24, 2005 Srini devadas and Eric Lehman Lecture notes Number theory ll Image of Alan Turing removed for copyright reasons s The man pictured above is Alan Turing, the most important figure in the history of mputer science. For decades, his fascinating life story was shrouded by government secrecy, societal taboo, and even his own deceptions At 24 Turing wrote a paper entitled On Computable Numbers, with an Application to the Entscheidungsproblem. The crux of the paper was an elegant way to model a computer in mathematical terms. This was a breakthrough, because it allowed the tools of mathemat ics to be brought to bear on questions of computation. For example, with his model in hand, Turing immediately proved that there exist problems that no computer can solve- no matter how ingenius the programmer. Turings paper is all the more remarkable be cause he wrote it in 1936, a full decade before any computer actually existed The word"Entscheidungsproblem"in the title refers to one of the 28 mathematical problems posed by David Hilbert in 1900 as challenges to mathematicians of the 20th century. Turing knocked that one off in the same paper. And perhaps you',ve heard of the"Church-Turing thesis"? Same paper. So Turing was obviously a brilliant guy who generated lots of amazing ideas. But this lecture is about one of Turings less-amazing deas. It involved codes. It involved number theory. And it was sort of stupid 1 Turing s Code Let's look back to the fall of 1937. Nazi germany was rearming under Adolf Hitler, world- shattering war looked imminent, and-like us- Alan Turing was pondering the useful6.042/18.062J Mathematics for Computer Science February 24, 2005 Srini Devadas and Eric Lehman Lecture Notes Number Theory II Image of Alan Turing removed for copyright reasons. The man pictured above is Alan Turing, the most important figure in the history of computer science. For decades, his fascinating life story was shrouded by government secrecy, societal taboo, and even his own deceptions. At 24 Turing wrote a paper entitled On Computable Numbers, with an Application to the Entscheidungsproblem. The crux of the paper was an elegant way to model a computer in mathematical terms. This was a breakthrough, because it allowed the tools of mathemat￾ics to be brought to bear on questions of computation. For example, with his model in hand, Turing immediately proved that there exist problems that no computer can solve— no matter how ingenius the programmer. Turing’s paper is all the more remarkable be￾cause he wrote it in 1936, a full decade before any computer actually existed. The word “Entscheidungsproblem” in the title refers to one of the 28 mathematical problems posed by David Hilbert in 1900 as challenges to mathematicians of the 20th century. Turing knocked that one off in the same paper. And perhaps you’ve heard of the “Church­Turing thesis”? Same paper. So Turing was obviously a brilliant guy who generated lots of amazing ideas. But this lecture is about one of Turing’s less­amazing ideas. It involved codes. It involved number theory. And it was sort of stupid. 1 Turing’s Code Let’s look back to the fall of 1937. Nazi Germany was rearming under Adolf Hitler, world￾shattering war looked imminent, and— like us— Alan Turing was pondering the useful­