Dana Scott
Visiting Scholar, UC Berkeley

A Semantics for Randomness

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.

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. 

Thursday, October 22, 2015
2:00 PM
Gates & Hillman Centers 6501

Principles of Programming Seminars