Abstract:
Many authors have suggested ways of adding random elements and probability assessments to versions of Church's Lambda-Calculus. Recently the speaker realized that the so-called Graph Model (based on using enumeration operators acting on the powerset of the integers) could easily be expanded to include random variables taking values in the powerset. The talk will also report on how a continuation-passing semantics can be used for modeling a branching combinator using random coin tossing. The idea can also be employed for introducing many other random combinators.
Bio: Scott was born in Berkeley, California in October of 1932. He studied at UC Berkeley (B.A. 1954) and then at Princeton (Ph.D. 1958 under Alonzo Church). He has held academic appointments at Chicago (1958-60), UC Berkeley (1960-63), Stanford (1963-69), Amsterdam (1968-69), Princeton (1969-72), Oxford (1972-81), Linz, Austria (1992-93), and finally Carnegie Mellon University (1981-2003). He received honorary doctorates from Utrecht (1986), Darmstadt (1995), Edinburgh (1995), Ljubljana (2003), and St Andrews, Scotland, (2014). He was awarded several prizes, most notably the ACM Turing Award (jointly with Michael Rabin) (1976), the Rolf Schock Prize, Royal Swedish Academy of Sciences (1997), and the Gold Medal of the Sobolev Institute of Mathematics, Novosibirsk, (2009). He is a Fellow of the British Academy and the US National Academy of Sciences. Scott supervised the Ph.D. theses of 51 students, some solely, some jointly. He and his wife currently reside in Berkeley after retirement, where he is a Visiting Scholar in Mathematics at UC Berkeley.