Faculty of Information Technology, Monash University, Friday 14 September, 2012
Alan Turing (1912-1954) was a remarkably versatile and original mathematician and computer scientist, indeed he helped create the field of computer science. He made major contributions in several areas including the theory of computability, breaking the Enigma code during World War 2, design of early computers, and artificial intelligence. He died tragically at age 41. This year is the centenary of his birth and his achievements are being celebrated in Alan Turing Year, an international programme of events including this one.
Venue: Lecture theatre R4, Rotunda, building 8, Clayton campus.
|9:10am||Graham Farr||Alan Turing|
|9:25am||David Albrecht||Turing machines|
|9:55am||James Harland (RMIT)||Turing and ordinal logic|
|10:05am||Carlo Kopp||Military context of Turing’s work at Bletchley Park|
|10:10am||Ron Steinfeld||Turing and the Enigma cypher|
|10:55am||Doug Hamilton||Commentary on chess game: Turing’s Algorithm v. Garry Kasparov|
|11:10am||Group photo in R4|
|11:15am||Arun Konagurthu||Turing and Morphogenesis|
|11:35am||Kevin Korb||The Turing Test|
|11:55am||David Dowe||Universal Turing Machines, probability and intelligence|
This talk is about the life of Alan Turing, to give some personal context to the scientific contributions discussed in the other talks. We cover his family background, the main influences on his scientific development, the chronology of his main positions and achievements, his academic family tree, his attributes as a mathematician, and his personal characteristics.
In his groundbreaking paper, “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936), Alan Turing introduced the notation of a computing Machine. These machines are now known as Turing Machines and come in a variety of forms. In this talk we introduce a simple version of a Turing Machine, and show how it can be used to represent a simple function like doubling natural numbers. We will also describe how a Turing Machine represented in a form so that it can be used as input in another Turing Machine. This leads to the notation of a Universal Turing Machine, which can be considered as a representation of a programmable computer.
Can we tell whether a computer program, or a Turing machine, will halt on a given input, or if it will loop forever? A decision problem consists of two parts: a generic instance or input and a yes-no question about that input. A decision problem is computable if there exists a Turing machine that for any given input will halt with the answer for that input. Turing showed that the problem of deciding if a Turing machine will halt on a given input is uncomputable. Unfortunately, it follows that there is no program to check if a program will not loop forever on some input.
The Entscheidungsproblem answer to an audience member’s question discusses three desirable attributes of a mathematical system: consistency, completeness and decidability. Towards the end, three approaches to computability developed in the 1930s are alluded to, but not all are named. These are: recursive function theory (Kurt Goedel), lambda calculus (Alonzo Church) and Turing machines. The statement that Goedel “took care of the first two” applies to the desired attributes of a mathematical system, not to the approaches to computability.
Godel had shown that any mathematical theory of sufficient strength is incomplete, i.e. contains statements that are true but unprovable in that theory. Turing addressed this problem by using the transfinite methods of Cantor to add an infinite number of statements to a theory so that it becomes complete. This is not without cost, which is that the notion of ‘proof’ has to be relaxed to include an ‘oracle’, which can be consulted to supply information that cannot be finitely constructed. This was Turing’s PhD work, completed in eight months.
Mostly, when we consider Alan Turing’s achievements, we look at the long term impact of his work, over the decades. Less well appreciated is the enormous importance of his work in cryptography, cracking the German Enigma cipher. This short presentation discusses the critical strategic pressures Britain confronted during that period, especially the impact of the protracted Battle of the Atlantic.
Following on from the previous talk, this short talk explains why breaking the the German Enigma cipher was a formidable cryptographic challenge, and how Turing’s ingenious insights allowed this challenge to be overcome with the help of special purpose electromechanical computers, making an invaluable contribution to the Allied effort during WWII.
Alan Turing designed the first-ever chess-playing algorithm. It was quite simple, and he did not implement it on a computer. It was based on looking ahead a small, fixed number of moves. At the Turing Centenary Conference in Manchester, in June 2012, former World Chess Champion Garry Kasparov (generally reckoned to be the greatest chess player of all time) gave a talk about Turing’s chess algorithm and played a game against it.
Here, three-time Australian Chess Champion Doug Hamilton (also formerly an academic in the Faculty of IT at Monash) discusses Turing’s work on chess, computer chess in general, and takes you through this game between Turing’s algorithm and Kasparov. You can also see the game itself at: http://www.chessvibes.com/reports/garry-kasparov-versus-alan-turings-1950-chess-program
This short talk attempts to provide an overview of Turing’s work on Morphogenesis, his first and, sadly, his only work in Mathematical Biology. His seminal paper entitled “The chemical basis of morphogenesis” presented a groundbreaking model to explain developmental patterns observed in plants and animals. This is Turing’s most cited work to date, and indeed revolutionised, and still continues to revolutionalise, many areas of biology. This talk is constructed from a wide range of source materials on this subject.
The Turing Test marks the beginning and end of Artificial Intelligence (AI). Turing introduced it (as “the imitation game”) in his famous paper “Computing Machinery and Intelligence” (Mind, 1950) in a paper that began research in AI. The Test was meant to avoid endless debates over the nature of intelligence by offering a reasonably clear behavioral criterion for when an artifact might be considered to be intelligent. Thus, should the Test be passed, it will also mark the end of AI as a research program and its beginning as a reality.
The slides were prepared for a longer talk presented at the Singularity Summit Australia 2012, RMIT University, 18 August 2012. From this set of slides, the following were presented in this Turing Centenary Celebration talk: 1, 3-5, 22, 33, 41, 78+, 85, 86, 89 and 90.
Cutting the Turing Birthday Cake
The Turing Birthday Cake (design on cake icing by David Dowe supported by Joy Reynolds Graphic Design). The components of this picture represent four of Turing’s areas of activity: the outer circle is a cypher disc of the kind used in Vigenere cyphers, to represent Turing’s cryptographic work; the pattern on the cow represents morphogenesis; to right and above the cow (with stick figures and computer) is a schematic representation of Turing's (1950) Imitation Game (commonly known as the Turing test); and below that is a diagram of a simple Turing machine (specifically, its finite state control).