Lecture Notes for Introduction to Theory of Computation - Robert Daley.pdf

(4344 KB) Pobierz
Lecture Notes for CS 2110 Introduction to Theory of Computation
Next:
Forward
Lecture Notes for CS 2110
Introduction to Theory of Computation
Robert Daley
Department of Computer Science
University of Pittsburgh
Pittsburgh, PA 15260
●
Forward
●
●
Contents
1. Introduction
●
●
●
●
1.1
1.2
1.3
1.4
Preliminaries
Representation of Objects
Codings for the Natural Numbers
Inductive Definition and Proofs
●
2. Models of Computation
●
●
●
●
●
2.1
2.2
2.3
2.4
2.5
Memoryless Computing Devices
Digital Circuits
Propositional Logic
Finite Memory Devices
Regular Languages
●
3. Loop Programs
●
●
●
3.1 Semantics of
LOOP
Programs
3.2 Other Aspects
3.3 Complexity of LOOP Programs
http://www.cs.pitt.edu/~daley/cs2110/notes/cs2110w.html (1 of 3) [12/23/2006 12:00:41 PM]
Lecture Notes for CS 2110 Introduction to Theory of Computation
●
4. Primitive Recursive Functions
●
●
●
●
●
●
4.1
4.2
4.3
4.4
4.5
4.6
Primitive Recursive Expressibility
Equivalence between models
Primitive Recursive Expressibility (Revisited)
General Recursion
String Operations
Coding of Tuples
●
●
●
5. Diagonalization Arguments
6. Partial Recursive Functions
7. Random Access Machines
●
●
●
●
●
7.1
7.2
7.3
7.4
7.5
Parsing RAM Programs
Simulation of RAM Programs
Index Theorem
Other Aspects
Complexity of RAM Programs
●
8. Acceptable Programming Systems
●
●
8.1 General Computational Complexity
8.2 Algorithmically Unsolvable Problems
●
●
9. Recursively Enumerable Sets
10. Recursion Theorem
●
10.1 Applications of the Recursion Theorem
r
10.1.1 Machine Learning
r
10.1.2 Speed-Up Theorem
●
11. Non-Deterministic Computations
●
●
●
●
●
11.1
11.2
11.3
11.4
11.5
Complexity of Non-Deterministic Programs
NP-Completeness
Polynomial Time Reducibility
Finite Automata (Review)
PSPACE Completeness
http://www.cs.pitt.edu/~daley/cs2110/notes/cs2110w.html (2 of 3) [12/23/2006 12:00:41 PM]
Lecture Notes for CS 2110 Introduction to Theory of Computation
●
12. Formal Languages
●
●
●
●
●
●
●
12.1
12.2
12.3
12.4
12.5
12.6
12.7
Grammars
Chomsky Classification of Languages
Context Sensitive Languages
Linear Bounded Automata
Context Free Languages
Push Down Automata
Regular Languages
●
●
Bibliography
Index
Permission is granted for
personal (electronic and
printed) copies of this
document
such copy (or portion
thereof) is accompanied by
this copyright notice.
Copying for any commercial
use including books,
journals, course notes,
etc., is
Next:
Forward
Bob Daley
2001-11-28
©Copyright 1996
provided
that each
prohibited
.
http://www.cs.pitt.edu/~daley/cs2110/notes/cs2110w.html (3 of 3) [12/23/2006 12:00:41 PM]
Forward
Next:
Contents
Up:
Lecture Notes for CS 2110 Introduction to Theory
Previous:
Lecture Notes for CS
2110 Introduction to Theory
Forward
These notes have been compiled over the course of more than twenty years and have been greatly
influenced by the treatments of the subject given by Michael Machtey and Paul Young in
An
Introduction to the Genereal Theory of Algorithms
and to a lesser extent by Walter Brainerd and
Lawrence Landweber in
Theory of Computation.
Unfortunately both these books have been out of print
for many years. In addition, these notes have benefited from my conversations with colleagues
especially John Case on the subject of the Recursion Theorem.
Rather than packaging these notes as a commercial product (i.e., book), I am making them available via
the World Wide Web (initially to Pitt students and after suitable debugging eventually to everyone).
Next:
Contents
Up:
Lecture Notes for CS 2110 Introduction to Theory
Previous:
Lecture Notes for CS
2110 Introduction to Theory
Bob Daley
2001-11-28
©Copyright 1996
Permission is granted for personal (electronic and printed) copies of this document
provided
that each such copy (or
portion thereof) is accompanied by this copyright notice.
Copying for any commercial use including books, journals, course notes, etc., is
prohibited
.
http://www.cs.pitt.edu/~daley/cs2110/notes/cs2110w_node1.html [12/23/2006 12:01:17 PM]
Contents
Next:
1. Introduction
Up:
Lecture Notes for CS 2110 Introduction to Theory
Previous:
Forward
Contents
●
●
●
●
●
●
●
●
●
Contents
1. Introduction
r
1.1 Preliminaries
r
1.2 Representation of Objects
r
1.3 Codings for the Natural Numbers
r
1.4 Inductive Definition and Proofs
2. Models of Computation
r
2.1 Memoryless Computing Devices
r
2.2 Digital Circuits
r
2.3 Propositional Logic
r
2.4 Finite Memory Devices
r
2.5 Regular Languages
3. Loop Programs
r
3.1 Semantics of LOOP Programs
r
3.2 Other Aspects
r
3.3 Complexity of LOOP Programs
4. Primitive Recursive Functions
r
4.1 Primitive Recursive Expressibility
r
4.2 Equivalence between models
r
4.3 Primitive Recursive Expressibility (Revisited)
r
4.4 General Recursion
r
4.5 String Operations
r
4.6 Coding of Tuples
5. Diagonalization Arguments
6. Partial Recursive Functions
7. Random Access Machines
r
7.1 Parsing RAM Programs
r
7.2 Simulation of RAM Programs
r
7.3 Index Theorem
r
7.4 Other Aspects
r
7.5 Complexity of RAM Programs
8. Acceptable Programming Systems
http://www.cs.pitt.edu/~daley/cs2110/notes/cs2110w_node2.html (1 of 2) [12/23/2006 12:01:34 PM]

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin