Undergraduate Catalog 2020-2021

CSC 484 Theory of Computation(RNL)

4 hours; 4 credits. The notion of an algorithm. Primitive recursive and partial recursive functions. Turing machines and other models of computation. Markov algorithms. Church thesis. Godel numberings and unsolvability results. Halting problem. Post correspondence problem. Recursive and recursively enumerable sets. Concepts from formal language theory. Prerequisites: A grade of C or above in (CSC 126 or 270) and MTH 339 and (MTH 233 or 236).