Uncomputable through to finite state - Professor Brailsford explains Chomsky's hierarchy.

Turing and the Halting Problem:    • Turing & The Halting Problem - Comput...  
"Most Difficult Program" - Ackermann Function:    • The Most Difficult Program to Compute...  
Busy Beaver Turing Machines:    • Busy Beaver Turing Machines - Compute...  
Finite State Automata:    • Computers Without Memory - Computerphile  
Reverse Polish & The Stack:    • Reverse Polish Notation and The Stack...  
Programming in Postscript:    • Programming in PostScript - Computerp...  

Professor Brailsford's Notes: http://bit.ly/computerphile_Chomsky
Professor Brailsford's t-shirt kindly supplied by Peleg Bar Sapir

  / computerphile  
  / computer_phile  

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

Computerphile is a sister project to Brady Haran's Numberphile. More at http://www.bradyharan.com