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 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, 2010Time: 5:30 pmLocation: Wean Hall 8220Submitted by:  Daniel Spector