Theory of Computability
Download as PDF
Overview
Subject area
CSC
Catalog Number
I2200
Course Title
Theory of Computability
Department(s)
Description
Formulations of effective computability: Sheperdson-Sturgis machines. Turing type models, recursive functions, and semi-Thue systems. The equivalence of the various formulations. ChurchÆs Thesis. Fundamental theorems of computability: universal machines, S-M-N, and recursion theorem. Unsolvable problems. Recursive and r.e. sets.
Academic Career
Graduate
Liberal Arts
No
Credits
Minimum Units
3
Maximum Units
3
Academic Progress Units
3
Repeat For Credit
No
Components
Name
Lecture
Hours
3
Requisites
019795