Extending the scope of the Church Turing Thesis

by · May 9, 2017 · 194 views ·


The first premise of denotational semantics is that programs may be viewed as names for mathematical objects. Because recursion is an essential feature of programming, some care needs to be taken in defining the structures within which one may find denotations. As an example, it is well-known that ordinary recursion theory deals with partial functions from $\mathbf{N}$ to $\mathbf{N}$, rather than total ones. The second premise is that the semantics should be compositional, that is, the denotation of a program should be built from the denotations of its parts. From this one derives the requirements that denotational spaces, the "domains'' of Dana Scott's mathematical theory of computation, should be amenable to the constructions of programming languages. In this talk we will first review these requirements in some detail and then focus on one construction in particular, known as the probabilistic powerdomain. Although the object of intense investigation over the last 25 years, it is not known whether the probabilistic powerdomain construction fits within Scott's denotational semantics. As we will explain, the problem can be reduced to the existence of certain functions on weighted finite posets.