MATH 459, Computability and Unsolvability, Spring 1998
  MWF 9:05-9:55 AM, 316 Boucke, Schedule Number 386658, 3 credits
  Stephen G. Simpson, simpson@math.psu.edu
  http://www.math.psu.edu/simpson/

Textbook: Nigel Cutland, Computability: An
Introduction to Recursive Function Theory, Cambridge University
Press, ISBN 0-521-29465-7 (paperback).

Prerequisites: This course is suitable for advanced
undergraduate and beginning graduate students in mathematics and
computer science.  There are no specific prerequisites.

Course Description:

This course is an introduction to the mathematical theory of
computability and non-computability.  An example of a computable
function is the Ackermann function.  Non-computable sets and
unsolvable decision problems arise naturally in several branches of
mathematics, including number theory (Diophantine equations) and group
theory (word problems).  We shall explore several of these
applications.

If time permits, we may prove the famous theorem of Matijasevic,
which characterizes recursively enumerable sets of integers as
Diophantine sets.  It follows that there can be no general algorithm
to decide whether a given polynomial equation with integer
coefficients has a solution in integers.  This provides a negative
solution to Hilbert's 10th problem.

Another topic that we may explore is computable analysis.  We can give
an example of a continuous, computable, real-valued function  on
the closed unit interval  such that the maximum value of  is
a non-computable real number.

One fascinating result of pure computability theory is the Recursion
Theorem, which may be paraphrased as follows.  Whenever we are writing
an algorithm to compute the values of a given number-theoretic
function , we may always assume that we are already in possession
of a description of the algorithm in question.  In other words, we may
always define  recursively, in terms of itself.  This theorem has
remarkable consequences related to paradoxes of self-reference.