Graduate Students
Graduate Programs     
Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students

Apply Now
Graduate Seminar

William Gunther
Carnegie Melllon University
Title: Lambda Calculus and the Decision Problem

Abstract: In 1928, Alonzo Church formalized the $lambda$-calculus, which was an attempt at providing a foundation for mathematics. At the heart of this system was the idea of function abstraction and application. In this talk, I will outline the early history and motivation for $lambda$-calculus, especially in recursion theory. I will discuss the basic syntax and the primary rule: $beta$-reduction. Then I will show how one would represent certain structures and control statements (numbers, pairs, if-then-else statements, etc) in this system. This will lead into some theorems about fixed points which will allow us to have some fun and (if there is time) to supply a negative answer to Hilbert's Entscheidungsproblem: is there an effective way to give a yes or no answer to any mathematical statement.

Date: Tuesday, November 9, 2010
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Daniel Spector