Yuri Gurevich from Microsoft Research [1] gave a very erudite and somewhat interesting Google Tech Talk on the Church-Turing thesis today. The reward for patiently listening to a poor video quality H.323 session across the Atlantic at midnight was the discovery of something totally new: Abstract State Machines.
Update (The Video is Up):
I have trouble understanding ASMs as a fundamental model for computation like Lambda Calculus or Post-Turing Machines. But apparently “States” and “State Transitions” are good enough for universality. The advantage over the Standard Models is supposed to be the expresiveness and better mapping to high level structures and algorithms. This makes them very suitable for Formal Models , Verification and Validation. The video of the talk should be out soon and I will post a link when that happens. But the two most interesting personal takeaways from the talk were totally unrelated to ASMs:
- Kolmogorov’s physical view of computation, entropy and information is completely fascinating. I should really find a readable text on Algorithmic Information Theory.
- Donald Knuth once remarked on Artificial Intelligence: There are two great unsolved problems in AI – What is A ? and What is I ?
Even if I didn’t make out much else from the talk, Don’s snide humor was totally worth an hour 
[1] Yes, we do let people from Redmond into Googleplex – Stan needs to be fed once in a while.
Filed under: Computer Science, DEK, Humor
Oh and FWIW, Professor Vaughan Pratt was a member of the audience.
For the curious, many parts of the Church-Turing story including Bertrand Russell’s letter to Frege, is documented in Martin Davis’s wonderful book: “From Leibniz to Turing: The Universal Computer”