Friday, June 22, 2012

Turing Centenary

Today is the 100th anniversary of Alan Turing's birth, and Google has a nifty doodle representing a Turing machine as its doodle today. The Register links to a Dutch project that made a Turing Machine with Lego Mindstorms parts.

Exercise for the reader: explain how a Turing machine can generate all words in a recursively enumerable language, and generate all words in a recursive language in canonical order. Show your work.

No comments:

Post a Comment