CS430 2012-2013 | Reading Turing's 1937 Paper |
Alan Turing was one of the founders of Computer Science, along with Alonzo Church, Emil Post and others in the 1930s. In their (separate) 1936/7 papers, Church, Turing and Post had formulated the first formal definitions of what it means to be "computable", with Church and Turing discovering the first uncomputable problems, thus effectively launching the discipline of Computer Science. (You'll be studying some of the fruits of their work in your core CS355 and CS370 modules this year).
Turing's paper also had a number of other important contributions. He defined a "universal machine": one that could take a program as input instead of being hard-wired for a specific purpose, just like a modern computer. In justifying his thesis that his machines represented all computable functions, Turing showed them equivalent to Church's formalism, laying the foundation for the Church-Turing thesis. Finally, Turing also demonstrated that a general solution to Hilbert's Entscheidungsproblem was not possible.
As well as studying a central issue in Computer Science, these lectures will take a very specific and challenging approach to the topic by concentrating on the use of primary sources. That is, instead of using a textbook we'll be reading the actual 1937 paper itself. The idea is to bypass all interpretations, simplifications and explanations, and put you in direct contact with the words and ideas of Alan Turing himself, as one scientist to another.
2012 is the Turing Year Alan M. Turing was born in 1912 in London, and a series of events are taking place this year to celebrate his centenary.
CS430 2011-2012 | Understanding Post's Problem |
Emil L. Post was one of the founders of Computer Science, along with Alonzo Church, Alan Turing and others in the 1930s. While his original 1936 paper was not as comprehensive as those of either Church or Turing, his 1944 report on degrees of unsolvability broke new ground, and introduced what came to be known as "Post's problem".
In their 1936 papers, Church and Turing had formulated the first formal definitions of what it means to be "computable" and had independently discovered the first uncomputable problems, thus effectively launching the discipline of Computer Science. (You'll be studying some of the fruits of their work in your core CS355 and CS370 modules this year). Post's contribution in 1944 was to further explore the space of uncomputable problems, essentially by generalising their definition, and seeking to discover if there were different degrees of uncomputability.
As well as studying a central issue in Computer Science, these lectures will take a very specific and challenging approach to the topic by concentrating on the use of primary sources. That is, instead of using a textbook we'll be reading the actual 1944 paper itself. The idea is to bypass all interpretations, simplifications and explanations, and put you in direct contact with the words and ideas of Emil Post himself, as one scientist to another.
Welcome to the Great Conversation.
CS430 | Reading Church's Paper 2010-2011 |
Alonzo Church's paper An unsolvable problem of elementary number theory was presented to the American Mathematical Society on 19 April 1935 and published in the American Journal of Mathematics in 1936.
In this paper he breaks new ground by showing, for the first time, that a problem is undecidable: that it is not possible to develop an algorithm to solve it. In order to do this, Church had to develop a formal definition of the informal notion of "calculability" or, as it is called nowadays, computability. Thus, while this paper is an important (meta-)mathematical result, it is more important as the paper that marks the foundation of Computer Science as a discipline.
Barely a year later, Alan Turing published as similar result, though using a different formulation of "calculability". It is the equivalence of the various systems of Church, Kleene, Turing, Post and others that convinces us that these system do indeed capture the essence of computability.
In these six lectures we'll be reading the text of the actual theorem itself. The idea is to bypass all interpretations, simplifications and explanations, and put you in direct contact with the words of Alonzo Church himself, as one scientist to another. Welcome to the Great Conversation.
Alonzo Church, "An unsolvable problem of elementary number theory", American Journal of Mathematics, 58 (1936), pp 345-363.
This paper is also published in The Undecidable by Martin Davis, Dover, 1965 (ISBN: 0-486-43228-9).CS431 2009-2010 | Reading Gödel's Theorems |
In 1929 Kurt Gödel (at the age of 23) presented his PhD thesis, proving the completeness theorem for the first-order predicate calculus. However, he is better remembered for what followed when, in 1931, he presented his incompleteness theorems, displaying the limitations of formal systems for arithmetic. As well as being of fundamental mathematical importance, these theorems also laid the groundwork for the results of Church and Turing a few years later that gave birth to Computer Science.
In these lectures we'll be reading the actual theorems (in translation - the originals were in German), particularly On formally undecidable propositions of Principia Mathematica and related systems.