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

[Bill Rounds]

The point is that even to agree that what the sequential models
have in common is the concept of computable function, we have to
presuppose the concept of function. When TMs and the lambda calculus
were invented, the inventors were trying to qualify the function 
concept,
to say which functions were computable.

Sequential operating systems, on the other hand, aren't about functions
at all. They are about playing a game with the environment, a win
for the system  being the ability to continue the game forever. You 
could
even imagine a TM that took on this role, but that wasn't why TMs came
into existence.

Your last question is a good one, which has to do with being able to 
classify
all of the (admittedly mathematical) models in terms of a single 
device-independent
mathematical model of their behavior, and perhaps even their structure. 
That is
what Robin Milner is trying to do with his bigraphical reactive 
systems. The structural
part of the problem is one reason I am not sure that games are the 
complete answer.

Bill
On Sep 26, 2004, at 7:26 PM, Martin Berger wrote:

>> 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