Visiting Scholar, UC Berkeley

A Semantics for Randomness

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.

Principles
of Programming Seminars