=ADD=
=reftype=
14
=number=
01-27
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/2001/01-27.ps.gz
=year=
2001
=month=
12
=author=
Rolletscheck; Heinrich
=title=
Computability Theory (Lecture Notes)
=abstract=
These are lecture notes for a course on computability theory. The main topics
are:
\item{$\bullte$}Definition of the basci concepts (partial recursive, recursive
and primitive recursive functions, recursive, primitive recursive and recursively
enumerable sets) based on a primitive programming language.
\item{$\bullet$}Proof that many intuitively computable functions are indeed partial
recursive, and that the defined computability classes are closed under many
operations.
\item{$\bullet$}Construction of universal functions, S-m-n-theorem, diagonalization
method for proving negative results, basic properties of recursively enumerable sets.
\item{$\bullet$}Alternative ways to define the class of partial recursive functions
($\mu$-recursion, Turing machines, Markov algorithms).
\item{$\bullet$}Undecidability results, undecidability proofs by reduction, results
on enumeration, fixed-point theorem.
\item{$\bullet$}Basic theory of reducibility relations.