Fri Nov 15, 2013
60 Evans Hall, 4:10–6 PM
Dana S. Scott (Carnegie Mellon)
Many authors have suggested ways of adding random elements and probability assessments to versions of Church’s Lambda-Calculus. When asked recently about models, the speaker realized that the so-called Graph Model (based on using enumeration operators acting on the power set of the integers) could easily be expanded to allow random variables taking values in the model. Other models can be treated similarly. The talk will discuss randomizing algorithms and how a continuation-passing semantics can be used for modeling a branching combinator using random coin tossing. These ideas can also be employed for introducing many other kinds of random combinators.