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

[Rocha]

Hi! Greetings from Brazil!

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

   I think that nowadays computer science evolved to a point where
there is no concrete reason to still believe that the classical
theory of computation serves as a suitable theory for real computers. 
Not mention the need for support for new developments in computers.

   From my point of view, there are a handful of arguments that one can 
state in favor of that claim:

   1) domain-theoretic arguments: for instance, non-terminating 
computations are essential in real computers, but are considered 
meaningless in the classical theory of computation. This was already
pointed by domain theory: one of the most important conceptual 
contributions of domain theory to computer science id the notion of 
limit of computation, and that non-terminating computations need
not be trivialized and considered equivalent. One can assign possibly 
different meanings them by considering infinite limits (total elements) 
in the domain of the computation.

   2) interaction arguments: real computers are interactive machine. 
This comes well from the work of P.Wegner and D.Goldin work, and others, 
and goes hand in hand with the shortcomings of CTC exposed by process 
theory and theories of reactive systems, since their beginnings.

   I could add the other kinds of arguments here, but they are more 
interpretative than those two, and are less suitable to be stated in a 
discussion list. They concern features like, for instance, situatedness 
of real computers, that clearly do not apply to models of CTC.

   Situatedness is strongly dependent from interaction, but is more than 
that. A TM, for instance, operates like a closed system: after entering 
the input data, it computes in isolation from any environment, then it 
outputs the final data (if ever): no interaction during computation and, 
thus, no situatedness. And other aspects, besides situatedness could 
also be considered.

   Of course, one can always extend the models of CTC with some 
additional component that supports the previously absent feature. The 
argument above concerns the standard models, not possible extensions.

   Mandatory remark: the perment TM of P.Wegner and Dina does not fall 
into this class of extension: it was conceived precisely to surpass the 
CTC, not to sustain it beyond its limit!

   I hope I can manage to submit a paper to the workshop, with the full 
argument. The argument is not new, I have been developing it for a long 
time, so it has good chances to be consistent and convincing. Of course, 
as we say here, "age is no certificate" :-)

   All the best,

   Antônio Carlos

-- 
Antônio Carlos da Rocha Costa
Escola de Informática - UCPel