Chomsky Hierarchy - Computerphile

Uncomputable through to finite state - Professor Brailsford explains Chomsky’s hierarchy. Turing and the Halting Problem: “Most Difficult Program“ - Ackermann Function: Busy Beaver Turing Machines: Finite State Automata: Reverse Polish & The Stack: Programming in Postscript: Professor Brailsford’s Notes: Professor Brailsford’s t-shirt kindly supplied by Peleg Bar Sapir This video was filmed and edited by Sean Riley. Computer Science at the University of Nottingham: Computerphile is a sister project to Brady Haran’s Numberphile. More at