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

[GQ Zhang]

Martin's first example may be put in the
perspective of a universal TM, which, given
a TM/program and an input, produces an output.

Once your program gets compiled, you can
consider it ``terminated'' -- the output being a
**function/TM** which, given an input, produces an output.

So computers do ``terminate'', but it is not the
same as ``shut-down'' or ``broken''.

GQ Zhang

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

> [The Types Forum, 
> http://lists.seas.upenn.edu/mailman/listinfo/types-list]
>
>> 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
>