Time:  12:30  13:30 
Room: 
Wean Hall 8220

Speaker: 
Rick Statman Department of Mathematical Sciences CMU 
Title: 
Algebraic Structures Intrinsic to Functional Programming

Abstract: 
Lambda Calculus is the starting point of all functional programming. Since Church noticed the undecidability of the word problem for semigroups ([1]), it has been understood that certain algebraic strutures are embedded in lambda calculus. These include the B,I monoid ([2],[4]), the free Cartesian monoid which includes the positive part of the Freyd,Heller, Thompson group ([5],[6]), the profinite group of hereditary permutations ([3]), and the near semirings and b.a.d. algebras of [7]. In this talk we shall first survey the backgound results. Next we outline the theorem that that every semigroup with a recursively enumerable word problem is pointwise embeddable in the combinator semigroup. Finally we discuss an number of related results concerning embedding congruences and r.e. subsets of free semigroups. In particular, we show that the free monoid generated by an arbitrary r.e. subset of combinators can be represented as the monoid of all terms which fix a finite set of points.
