Models of Computation

Table of Contents


Turing Machines
Models of Computation and Algorithms
Turing Machine Components
Turing Machine Instructions
Turing machine Computation
Turing Machine Example
A Multi-State Example
State Diagrams
Other State Diagrams
Post-Class Activities

Properties of Turing Machines
A Big Leap!
Church-Turing Thesis
Solvable Problems and Unsolvable Problems
Some Solvable Problems for Turing Machines
The Halting Problem
Unsolvability of The Halting Problem
Other Unsolvable Problems
Practical Consequences

Comparison of Turing Machines and Finite State Machines
Comparison of Turing Machines and Finite State Machines - I
Comparison of Turing Machines and Finite State Machines - II



CS1104 Main Page
Last Updated 2000/11/12
© J.A.N. Lee, 2000