[TYPES] FInCo 2005: FOUNDATIONS OF INTERACTIVE COMPUTATION -- CFP

[Martin Berger]

> Maybe I can put it this way -- TMs, lambda - calculus, etc. are
> all at heart about the mathematical concept of function. Functions
> -- basically the computable ones, higher-order, whatever -- are what we 
> agree we are talking about. But what mathematical concept do process 
> calculi, ambients, etc.  embody? In my opinion, the best reponse to this 
> has been the mathematical  concept of ``game''. That gets at some aspects 
> of interaction, but I'm not sure it's everything.

i'm not sure i can agree that TMs, lambda calculi and the like are just about
computable functions. it's the other way round: computable functions are
what we agree these models have in common. to see that the computed functions
may be insufficient even in the classical sequential case, let's look at two
examples:

* sequential operating systems, something that, most computer scientists would
   agree, can be implemented by a TM. and yet, one of the key features of an OS,
   even a sequential one, is that it does not terminate. it does not have a
   return value. doesn't that mean the conventional understanding of observation
   of a TM is already too restrictive?

* consider the following program which is ubiquitous. you find some variant
   in most computers:

           every 0.125 seconds, switch between tasks.

   now the fact that switching happens every 0.125 seconds is somewhat critical,
   in the sense that using 0.0000000000000001 zeptoseconds or 9999999999 billion
   years instead would (probably) render the computer physically infeasible
   but surely humanly unusable. yet, neither TMs nor lambda calculi allow
   to express such timing constraints as far as I can see (although it is
   not hard to augment the models). again we have an instance of the
   usual sequential notion of observation being too coarse.

both examples, while probably too simplistic, suggest to me that the
conventional understanding of classical sequential models of computation,
in particular the sequential notion of observation that is tied in with
the functional understanding of sequential computation are less canonical
than is usually admitted.

i have another question: in what sense is a game or a function a more
mathematical (and by connotation more dignified) object than a turing machine
or a name passing synchronisation tree?

martin