Event Report: Turing 100 @ Persistent – The Theory of Computation
This is a liveblog of the Turing 100 @ Persistent Event.
The Turing Awards celebrate the achievements of some of the most influential computer scientists. Unfortunately, a lot of the professionals and students in computer science are not well versed with the work of Turing Award winners, and since this year is the 100th birth anniversary of Alan Turing, the Turing 100 @ Persistent Lecture series has been started with the hope of sparking an interest amongst the computer science and software community in looking at computer science in some depth.
For each lecture, one Turing Award recipient will be picked and a 90-minute talk will be given on the work of that person. One such lecture will happen on every 1st Saturday of every month until June 2013. The schedule can be see here
Today’s event features a talk about Alan Turing himself by Mathai Joseph, Advisor TCS, followed by a talk on Turing’s Theory of Computation by Vivek Kulkarni, a Principal Architect at Persistent Systems.
Alan Turing – by Mathai Joseph
These are some rough notes taken during the talk.
- Turing was the first person to provide a mathematical model for the concept of “computation” which could be used for mathematically proving things related to computation. This led to the concept of:
- computability – whether something can be computed by computers
- decidability – whether it is possible to
- He did all of this before getting a PhD
- Church – Turing Thesis
- Turing went to Princeton to Work with Alonzo Church
- Church had proved computability result using lambda calculus
- Church, Kleene, and Rosser had used recursive functions
- Turing showed that this could be shown much more simply using the Turing machine
- Did his PhD from Princeton in 1938
- Mathematical basis for computing
- intuitively understandable solution
- After his PhD, Turing went to Bletchley Park, which had the UK government’s main “decryption” center
- Bletchley Park was involved in cryptanalysis – breaking of codes
- Huge teams human analysts worked in shifts to break codes
- Turing joined and became a leader in cryptanalysis
- Bletchley Park relied on Turing to invent new, better methods for breaking codes
- He played a key part in deciphering the Enigma code that the Germans used during World War 2.
- After the war, Turing moved to Manchester to work on:
- Computer Design
- Program Verification
- One of Turing’s lasting legacies is the study of complexity of algorithms
- There is a long history of interest in this area
- Ancient Greeks did it. Mathematicians in Kerala did it.
- Mathematicians did it too: Cantor, Hilbert, Pocklinton, Post, Church, Turing
- Given a strong base in 1960s – Hartmanis and Stearns formally quantified time & space of a computation in terms of number of steps taken by a Turing machine to complete the computation, and the total number of cells used on the tape. Obviously, Turing machines were key to this analysis. Without it, characterising the problem would have been much more difficult.
- Computer Science without Turing Machine?
- Difficult to imagine
- Something else would have evolved but:
- Would have taken longer to find
- Would have been harder to understand
- Would have been of less practical use
- Turing was 42 when he died (by cyanide poisoning – unclear whether it was a suicide or an accident)
- We can only guess what he might have done if he had lived longer
- A remarkable mind: mathematician, scientist, engineers and 100% genius
Turing’s Theory of Computation – by Vivek Kulkarni
This talk was an in-depth look at the theory of computation, covering:
- The concept of a state machine
- Determinism and non-determinism
- The concept of a Turing Machine
- Solvable and semi-solvable problems
- Godel numbering and Turing machine encoding
- The Universal Turing Machine
- The Halting Problem
- Multi-tape Turing Machines
Unfortunately, the talk was quite technical, and it is not easy to blog about it, especially without diagrams (which are quite important when you need to understand state machines and Turing machines, hence unfortunately, this live blog ends here.)
The next talk in this series will be on 4th August where Prof. Sham Navathe, from Georgia Tech University, USA, who is visiting Pune, will talk about the work of Ted Codd, the inventor of relational databases.