From the DAI mailing list... From: hewitt@ai.mit.edu Subject: SRI CSL Seminar June 13 Date: Tue, 7 Jun 1994 20:00-0400 Peter Wegner wrote Date: June 7, 1994 re: MODELS AND PARADIGMS OF INTERACTION "The evidence that interactive problem solving cannot be expressed by computable functions appears overwhelming. The nonalgorithmic nature of interactive computation contradicts Church's hypothesis that the intuitive notion of computability is captured by Turing computability." Dear Peter, Welcome to the club! As you are no doubt very well aware, the Message Passing Semantics Group and others have published numerous papers on this result for the last two decades. In fact, as far as I am concerned, this is one of the fundamental principles of multi-agent and concurrent systems. The first paper published was: Hewitt, C. E., Peter Bishop, and Richard Steiger, ``A Universal Modular Actor Formalism for Artificial Intelligence'' {\it Proceedings of 1973 International Joint Conference on Artificial Intelligence}. August 1973. pp. 235-245. This was followed by axiomatization of these systems in: Hewitt, C. E. and H. Baker, ``Actors and Continuous Functionals'' in {\it Formal Description of Programming Concepts} Erich J. Neuhold. (editor) Proceedings IFIP Working Conference on Formal Description of Programming Concepts, August 1-5, 1977, pp. 367-387. Hewitt, C. E. and H. Baker, ``Laws for Communicating Parallel Processes'' {\it IFIP-77}, August 1977, pp. 987-992. Baker, H. and C. E. Hewitt, ``The Incremental Garbage Collection of Processes,'' {\it Proceedings of the Symposium on Artificial Intelligence and Programming Languages}, SIGPLAN Notices {\it 12}, 55-59, August 1977. Baker, Henry, ``Actor Systems for Real-Time Computation,''MIT Phd. January 1978. in conjunction with the development of the proof theory of such systems in: Hewitt, C. E. et. al. ``Actor Induction and Meta-evaluation'' {\it Conference Record of ACM Symposium on Principles of Programming Languages}, January 1974. Hewitt, C. E. and R. Atkinson ``Synchronization in Actor Systems'' {\it Proceedings of Conference on Principles of Programming Languages} January 1977, pp. 267-280. Yonezawa, Aki, ``Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics,'' MIT Phd. December 1977. Yonezawa, A. and C. E. Hewitt ``Modeling Distributed Systems,'' {\it Proceedings of 1977 International Joint Conference on Artificial Intelligence}, August, 1977, pp. 189-198. Also in {\it Machine Intelligence 9}. John Wylie. 1978. Atkinson, R. ``Automatic Verification of Serializers'' MIT Phd. February 1980. in conjunction with the development of operational semantics of such systems in: Greif, Irene, ``Semantics of Communicating Parallel Processes,'' MIT Phd. August 1975. in conjunction with the development of denotational semantics of such systems in: Clinger, Will, ``Global Time and Actors,'' Phd. June 1981. in conjunction with the development of Open Systems Science for such systems in: Hewitt, C. E., de Jong, P., ``Open Systems'' MIT Artificial Intelligence Memo 692. 1982. Hewitt, C. E., de Jong, P., ``Message Passing Semantics as a Foundation for Reasoning'' MIT Artificial Intelligence Memo 245. 1983. Hewitt, C. E., ``Some Fundamental Limitations of Logic Programming'' MIT, Artificial Intelligence Memo 748. November 1983. Hewitt, Carl E., ``The Challange of Open Systems,'' {\it Byte Magazine}, Vol. 10, No. 4, April 1985, pp. 223-242. and the publication of the first paper on on inheritance vs. delegation in such systems: Hewitt, C. E., Attardi, G., and Lieberman, H. ``Delegation in Message Passing'' {\it Proceedings of First International Conference on Distributed Systems}. Huntsville. October 1979. All of these fundamental results were known and published a decade ago. I am sure that present and former members of the Message Passing Semantics Group would be pleased to answer any questions that you might have about this published literature. Sincerely, Carl P.S. Of course, there have been exciting new results published in the last decade as well including the work of Girard, Manna, Milner, Pnueli, and Rumbaugh which you cite. I believe that you should also cite the work done in the last decade by the DAI, MACC, and MAAMAW communities in addition because they have done equally fundamental work on different aspects of such systems from the ones that you cite. ------------------------------ From: Peter Wegner Subject: Response Date: Thu, 9 Jun 1994 09:47:56 -0400 Carl. In response to your note welcoming me to the club, I have been a "member of the club" since the 1960s, when I argued that assignment could not be modeled by functions and that operational semantics could not be captured by denotational semantics. There are many different roads that lead to the conclusion that the Church-Turing model is an inadequate foundation for computer problem solving, and I like to think of researchers in all these different areas as belonging to the club. I have always regarded actors as an important example of models of interaction, but I was not aware of any explicit discussion of inadequacy of the Church-Turing hypothesis or of the hypothesis that message passing computations could not be characterized by computable functions. I would be interested in specific quotes on this. My initial assertion that the evidence for the inadequacy of Church-Turing models was overwhelming was a way of saying that there is an overwhelming amount of research that implicitly points to this result. I agree that some degree of historical priority should be accorded to your work. In fact, your work and that of Gul is generally mentioned quite prominently by most researchers who discuss the foundations of message passing and concurrency, and I will continue to mention it in future discussions of foundations. However, my abstract focused on recent theorerical and software engineering evidence for the inadequacy of the Church-Turing hypothesis, and I therefore quoted Milner, Manna-Pnueli, Girard, Rumbaugh, and CORBA rather than the older actor work. My full abstract (from which you quote) is given below for the benefit of persons on your cc list who might not have seen it. peter ps: Here is the full abstract (of my talk at SRI on June 13 1994), from which Carl has quoted the initial part. Models and Paradigms of Interaction Peter Wegner, Brown University Abstract for talk at SRI: The evidence that interactive problem solving cannot be expressed by computable functions appears overwhelming. The nonalgorithmic nature of interactive computation contradicts Church's hypothesis that the intuitive notion of computability is captured by Turing computability. We provide evidence for this strong assertion by showing that: the observable behavior of objects cannot be expressed by computable functions state-dependent procedures of an object's interface are not computable functions requirements for programming in the large are not expressible by functions This evidence is reinforced by the non-functional nature of undisciplined concurrency (Milner Turing lecture, CACM Jan 1993) and the nonalgorithmic nature of reactive systems (Manna and Pnueli, Springer Verlag 1991). The weight of this evidence suggests that equating intuitive computability with Turing-machine computation is simplistic and inaccurate and that new models are needed to capture the richness of interactive computation. Models of interaction such as Milner's Pi calculus, Girard's linear logic, Rumbaugh's less formal but more practical object modeling technique OMT, and interface definition languages that form the basis of object management frameworks like CORBA are data points in a space of interactive modeling. These models share the view of computation as interaction among autonomus noun-like components rather than transformation by sequential verb-like functions, suggesting a general framework for models and paradigms of interaction.