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 Matijasevič, 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 f on the closed unit interval [0, 1] such that the maximum value of f 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 F, 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 F recursively, in terms of itself. This theorem has remarkable consequences related to paradoxes of self–reference.