Mathematics 291B: Recursion Theory

(Philosophy 351B--Enroll in Math 291B)

Spring 2005-2006

Syllabus

2. http://www.safalra.com/science/lambdacalculus/index.html

3. On-line books, lecture notes, etc (Lambda Calculus)

4. Barendregt and Barendsen's shorter introduction to the lambda calculus

5. Alonzo Church Papers

6. Church, Alonzo, An unsolvable problem of elementary number theory,

7. Church, Alonzo,

8.

2.

Motivation: Church and the lambda calculus

(Frege's `course-of-values')

**Apr 6**

Overview of Church's original result

Lambda terms and combinators: basic definitions

(Handout1)

(Homework1 to be handed in by Apr 18)

**Apr 11**

Lambda calculus: conversion, reduction, Church-Rosser

(Handout2)

**Apr 13**

Church-Rosser theorem for beta-reduction

(Handout3)

(Homework2 to be handed in by Apr 25)

**Apr 18**

Combinatory Logic: Terms, Conversion, Equality

(Handout4)

**Apr 20**

Combinatory Logic: Terms, Conversion, Equality (Cont.)

(Homework3 to be handed in by May 2)

**Apr 25**

The Power of Lambda and Combinators

(Handout5)

**Apr 27**

Representing the Recursive Functions

(Handout6)

(Homework4 to be handed in by May 9)

**May 2**

Representing the Recursive Functions (cont.)

**May 4**

Typed terms

Type assignment

(Handout7)

**May 9**

(no class)

**May 11**

(no class)

**May 16**

David Fernandez: The undecidability theorem

**May 18**

(no class)

**May 23**

Kentaro Fujimoto: The formal theories lambda-beta and CLw

**May 25**

Tomohiro Hoshi: Kripke-style semantics for typed lambda-calculus

**May 30**

Ryan Wisnesky: Models of the lambda-calculus

**Jun 1**

Ryan Wisnesky: Models of the lambda-calculus (cont.)

**Jun 6**

Jesse Alama: Type assignment in combinatory logic

**Jun 8**

Jesse Alama: Type assignment in combinatory logic (cont.)

**Jun 12**

Alexei Angelides: Dialectica interpretation

*Last updated: June 14, 2006, 09:23am PDT*