Deterministic Computation

Deterministic Computation

Lecture #2: Multi-Tape Turing Machines and the Cobham-Edmonds Thesis

• Lecture Notes
• Supplemental Material
• Exercise

Reading Exercise #2: Multi-Tape Turing Machines — A Better Simulation

• Assigned Reading

Lecture #3: Universal Turing Machines

• Lecture Notes
• Supplemental Material
• Exercise

Reading Exercise #3: A Review of the Diagonalization Method

• Assigned Reading

Lecture #4: Properties of Deterministic Complexity Classes

• Lecture Notes
• Supplemental Material
• Exercise

Lecture #5: Reductions and Reducibilities

• Lecture Notes
• Supplemental Material
• Exercise

Reading Exercise #4: Oracle Turing Machines and Oracle Reducibility

• Assigned Reading

Assignment #1: Universal Turing Machines and Deterministic Time Hierarchies

• Problems To Be Solved

cpsc 511/611 computer science faculty of science u of c

CPSC 511/611 intro to course deterministic computation nondeterministic computation space-bounded computation circuit computations randomzation, interaction and approximation structured models other topics assignments tests