p
Ma 117b:  Computability Theory (Winter 2016-17)

## ANNOUNCEMENTS

Registration for Winter term opens Thursday, November 17, 2016.

## COURSE DESCRIPTION

In the Winter term, we will discuss computability in the broader setting of mathematics. Some of the highlights here are a development of the Godel Incompleteness Theorems, the Boone-Novikov theorem on the undecidability of the word problem for groups, and the basics of the theory of algorithmic randomness. We will also discuss many examples of undecidable problems from logic, number theory, group theory, combinatorics, and computer science. No prior knowledge of any of these subjects is assumed. We will develop all the necessary background.

In the Spring term, we will start with a discussion of decidable problems, i.e., problems for which there are actually algorithms for their solution. Then we will introduce the basic concepts of the theory of computational complexity of algorithms. We will study the concept of feasible (polynomial time) computation and the relationship between deterministic polynomial (P) and nondeterministic polynomial (NP) computations, including NP-complete problems and the famous "P = NP" problem. We will also discuss probabilistic algorithms and derandomization.

TBA

## SCHEDULE

TR 13:00 - 14:25, 159 Sloan.

## INSTRUCTORS

Martino Lupini
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
Sloan 260
626-395-4340

None

Mondays at 5pm

## POLICIES

There will be no final exams. The grade will be based on 6 written assignments.

### Homework Policy

There will be 6 homework assignments consisting of three questions each. The assigments will be due on

1) Tuesday Jan 24th

2) Tuesday Jan 31st

3) Thursday Feb 16th

4) Tuesday Feb 21

5) Tuesday Feb 28

6) Tuesday March 7

Each assignment will be posted on this website two weeks before the due date.

## TOPICS COVERED

Lecture 1, Jan 5: Review of notions from the first part of the course, including the notion of primitive recursive function, computable function, decidable predicate, and recursively enumerable predicate. Given a total function α, definition of the notion of function computable in α. Discussion about the operational interpretation of function computable in α.

Lecture 2, Jan 10: Kleene normal form theorem for functions computable in α. Definition of Turing reducibility and Turing degrees.

Lecture 3, Jan 12: Equivalent characterization of Turing reducibility in terms of computable monotone functions from finite sequences of natural numbers to finite sequences of natural numbers.

Lecture 4, Jan 17: Construction of two functions that are Turing-incomparable. Notion of many-to-one reducibility and complete sets. The class of recursively enumerable sets with respect to α has complete sets. The class of computable sets with respect to α does not have complete sets.

Lecture 5, Jan 24:  The arithmetical hierarchy. Post's theorem. Turing jumps.

Lecture 6, Jan 26: Recap on first order logic (languages, structures, formulas, satisfaction).

Lecture 7, Jan 31: Gödel's theorem on arithmetic sets (part 1)

Lecture 8, Feb 2: Gödel's theorem on arithmetic sets (part 2). Statement of the Matiyasevich representation theorem and its consequences.

Lecture 9, Feb 7: Proof of the Matiyasevich representation theorem (part 1)

Lecture 10, Feb 9: Proof of the Matiyasevich representation theorem (part 2)

Lecture 11: Notion of formal deductive system and formal proof. Axioms for our formal deductive system, and statement of Godel's completeness theorem. Godel numbers of formulas. Recursive sets of formulas.

Lecture 12: Notion of theory, complete theory, recusively axiomatizable theory. Proof of Tarski's theorem: the complete theory of N is not arithmetical.

Lecture 13: Representable predicates and function in a theory T. Godel's first incompletness theorem. The axioms for Robinson's arithmetic Q and Peano Arithmetic.

Lecture 14: Proof that Q correctly computes arithmetic operations in N. The fixed point lemma for formulas.

Lecture 15: Rosser's proof of Godel's incompleteness theorem. Discussion on Godel's second incompleteness theorem. Examples of statements independent from Peano Arithmetic: Paris-Harrington's Ramsey theorem. and Goodstein's theorem on Goostein sequences.

Lecture 16: Strongly undecidable structure. Notion of definability of a structure in another structure. Theorem: if A is definable in A' and A is strongly undecidable, then A' is strongly undecidable. The following structures are strongly undecidable: the natural numbers in the language of arithmetic, the integers in the language of rings, the rationals in the language of fields, the group of permutations of an infinite set in the language of groups. Therefore the theories of rings, fields, and groups are undecidable.

Leture 17: Theorem : if A is definable with parameters in A' and A is strongly undecidable, then A' is strongly undecidable. There exist a strongly undecidable graph and a strongly undecidable lattice. As a consequence, the theories of graphs, lattices, and posets are undecidable.

## TEXTBOOK

There is no textbook for this course.  Here is a list of books on computability theory:

• H. Hermes, Enumerability, Decidability, Computability, Springer-Verlag, 1970.
• Y. Manin, A Course in Mathematical Logic for Mathematicians, Springer, 2010.
• M. Carey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
• Handbook of Mathematical Logic, J. Barwise, Ed., North-Holland, 1977.
• M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, North-Holland, 1978.
• A. Yasuhara, Recursive Function Theory and Logic, Academic Press, 1971.
• G. Boolos, J. Burgess and R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 2002.
• N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge Univ. Press, 1980.
• M. Davis, Computability and Unsolvability, Dover, 1985.
• E. Engeler, Introduction to the Theory of Computation, Academic Press, 1973.
• M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
• B. Trakhtenbrot, Algorithms and Automatic Computing Machines, D.C. Heath, 1963.
• A. Malcev, Algorithms and Recursive Functions, Noordhoff, 1970.
• H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1997.
• H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987.
• G. Tourlakis, Theory of Computation, Wiley, 2012.
• H. Enderton, Computability Theory, Academic Press, 2011.
• M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
• M. Davis, R. Sigal and E. Weyuker, Computability, Complexity and Languages, Morgan Kaufmann, 1994.
• R. Weber, Computability Theory, Amer. Math. Society, 2012.
• D. Bridges, Computability: A Mathematical Sketchbook, Springer, 1994.

Date Description

## HOMEWORK

Due Date Homework Solutions
January 24th Assignment 1
January 31st Assignment 2
February 16th Assignment 3
February 21st Assignment 4
February 28th Assignment 5
March 7th Assignment 6