05-28-1936 Turing Machines and Automata
|
|
| Audience/Grade: | College Freshman-College Senior |
| Discipline(s): |
Computer Engineering Computer Science Electrical Engineering Information Technology Software Engineering |
| Special Topic(s): | |
| Learning Resource Type: |
Community - Blog |
| Media Type: |
Unknown |
| Author(s): |
Susan Rodger |
| Description: | Engineering Pathway's "Today in History" blog for May 28. Excerpt: "Today in History - May 28, 1936 - "Turing Machine" paper submitted, his first paper on decidability. Turing's achievements at Cambridge had been on account of his work in probability theory. However, he had been working on the decidability questions since attending Max Newman's course on the foundations of mathematics. In 1936 he published "On Computable Numbers, with an application to the Entscheidungsproblem." It is in this paper that Turing introduced an abstract machine, now called a 'Turing machine', which moved from one state to another using a precise finite set of rules (given by a finite table) and depending on a single symbol it read from a tape. This is a classic paper that I hand out every year to students in my automata theory class to read about and write a summary. Turing machines are abstract, however, today students can get hands-on experience with Turing machines in a number of ways. First there are many simulation tools available for experimenting with Turing machines. I'll name just a few such as Turing's World (now out of print), Deus Ex Machina used in Taylor's book "Models of Computation and Formal Languages", and JFLAP. JFLAP is an extensive tool for building and simulating finite state machines, pushdown automata, and several versions of Turing machines. In addition one can experiment with LL and SLR parsing, L-Systems, and several construction proofs such as converting a NFA to a DFA to a minimal state DFA, or converting an NPDA to a CFG." |
| Rating: |
|
| Related Resources | |
| Keywords: | artificial intelligence computer science theory computational theory decidability entscheidungsproblem Turing machine autonoma |
| Is Component of: |
"Today in History" Blog of the Engineering Pathway Digital Library |
| References: |
JFLAP |
| Usage Tip | |
| Use of Resource: |
Susan Rodger has won awards for her creative courseware and approaches to teaching. She was co-author of JFLAP, a software tool that was finalist for the 2007 Premier Award. The figure above shows blueberry muffins with icing being used to demonstrate an edible Turing machine. |
| Difficulty: |
Difficult |
| Interactivity Level: |
Medium |
| Version Info | |
| Publication Date: | May 2008 |
| Platform/Format: |
WWW |
| Cost: |
Free |
| Download URL: | http://www.k-grayengineeringeducation.com/blog/index.php/2011/05/ |
| Metadata: |
IEEE LOM Record |
| Collection: |
NEEDS
|
