6.045J / 18.400J Automata, Computability, and Complexity, Spring 2005
This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines,...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Learning Object |
| Language: | en-US |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/68649 |
| Summary: | This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems. |
|---|