|
|
CSC 202 - Computability
Fall, Spring
Mathematical language of theoretical computer science (sets, n-tuples, relations,
functions, languages, predicates, quantifiers, proof methods such as induction,
diagonalization and the pigeonhole principle). The equivalence of various models
of computation (Church’s Thesis): Turing machines, extended Turing machines, nondeterministic
Turing machines, the m-recursive functions. Primitive recursive functions, Gödel
numbering, the halting problem, other unsolvable problems as time permits. Recursive
sets and recursively enumerable sets.
Prerequisites & Notes
CSC 161.
Credits: 3 s.h.
Add to Personal Catalog (opens a new window)
|
|