18.404J / 6.840J Theory of Computation, Fall 2002
A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, comple...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Learning Object |
| Language: | en-US |
| Published: |
2002
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/39661 |
| _version_ | 1826214952901279744 |
|---|---|
| author | Sipser, Michael |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Sipser, Michael |
| author_sort | Sipser, Michael |
| collection | MIT |
| description | A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. |
| first_indexed | 2024-09-23T16:13:24Z |
| format | Learning Object |
| id | mit-1721.1/39661 |
| institution | Massachusetts Institute of Technology |
| language | en-US |
| last_indexed | 2025-03-10T13:44:56Z |
| publishDate | 2002 |
| record_format | dspace |
| spelling | mit-1721.1/396612025-02-24T14:57:43Z 18.404J / 6.840J Theory of Computation, Fall 2002 Theory of Computation Sipser, Michael Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science computability computational complexity theory Regular and context-free languages Decidable and undecidable problems reducibility recursive function theory Time and space measures on computation completeness hierarchy theorems inherently complex problems oracles probabilistic computation interactive proof systems 18.404J 6.840J 18.404 6.840 A more extensive and theoretical treatment of the material in 6.045J/18.400J, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. 2002-12 Learning Object 18.404J-Fall2002 local: 18.404J local: 6.840J local: IMSCP-MD5-6ea338059dac8bc159125e8444494e71 http://hdl.handle.net/1721.1/39661 en-US Usage Restrictions: This site (c) Massachusetts Institute of Technology 2003. Content within individual courses is (c) by the individual authors unless otherwise noted. The Massachusetts Institute of Technology is providing this Work (as defined below) under the terms of this Creative Commons public license ("CCPL" or "license"). The Work is protected by copyright and/or other applicable law. Any use of the work other than as authorized under this license is prohibited. By exercising any of the rights to the Work provided here, You (as defined below) accept and agree to be bound by the terms of this license. The Licensor, the Massachusetts Institute of Technology, grants You the rights contained here in consideration of Your acceptance of such terms and conditions. text/html Fall 2002 |
| spellingShingle | computability computational complexity theory Regular and context-free languages Decidable and undecidable problems reducibility recursive function theory Time and space measures on computation completeness hierarchy theorems inherently complex problems oracles probabilistic computation interactive proof systems 18.404J 6.840J 18.404 6.840 Sipser, Michael 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title | 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title_full | 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title_fullStr | 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title_full_unstemmed | 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title_short | 18.404J / 6.840J Theory of Computation, Fall 2002 |
| title_sort | 18 404j 6 840j theory of computation fall 2002 |
| topic | computability computational complexity theory Regular and context-free languages Decidable and undecidable problems reducibility recursive function theory Time and space measures on computation completeness hierarchy theorems inherently complex problems oracles probabilistic computation interactive proof systems 18.404J 6.840J 18.404 6.840 |
| url | http://hdl.handle.net/1721.1/39661 |
| work_keys_str_mv | AT sipsermichael 18404j6840jtheoryofcomputationfall2002 AT sipsermichael theoryofcomputation |