Wegner OOPSLA'95, Interection vs Turing Machines (was: so-called Turing-Equivalence)

Massimo Dentico m.dentico@teseo.it
Sun, 29 Aug 1999 12:36:39 +0200

François-René‚ Rideau wrote:
> >: Tim Bradshaw <tfb@tfeb.org> on comp.lang.lisp
> > Another formalism of equivalent power to a UTM is the lambda
> > calculus
> I'm _sick_ of hearing such a meaningless statement of "being of
> equivalent power to a UTM" repeated over and over again as a bad
> excuse for bad programming language design.
> I question the meaningfulness of your term "Turing-equivalence".
> What definition of it do you use, if any?
> Equivalent _up to what transformation_?
> Do these transformation correspond to anything _remotely_
> meaningful *in presence of interactions with the external world
> (including users)*?

I  think  that  on  this  subject the paper  of  Peter  Wegner  is
illuminating.  Follows  a quotation of the  abstract  and  of  the
paragraph  2.3 because the original text is quite long (67  pages)
and  in  this  way you could have by yourselves  an  idea  of  the
content  and  you  could decide if you want to read  it  entirely.
However,  I  hope to don't annoy anyone with this  long  citation.
Sorry for my horrible English, any correction is wellcome.


                OOPSLA Tutorial Notes, October 1995

        Tutorial Notes: Models and Paradigms of Interaction
          Peter Wegner, Brown University, September 1995


The  development of a conceptual framework and formal  theoretical
foundation  for  object-based programming has  proved  so  elusive
because  the observable behavior of objects cannot be  modeled  by
algorithms.  The  irreducibility of object  behavior  to  that  of
algorithms  has radical consequences for both the theory  and  the
practice of computing.

Interaction  machines, defined by extending Turing  machines  with
input  actions (read statements), are shown to be more  expressive
than  computable  functions, providing  a  counterexample  to  the
hypothesis  of  Church  and Turing that the  intuitive  notion  of
computation   corresponds  to  formal  computability   by   Turing
machines.  The negative result that interaction cannot be  modeled
by algorithms leads to positive principles of interactive modeling
by  interface  constraints that support  partial  descriptions  of
interactive   systems  whose  complete  behavior   is   inherently
unspecifiable.  The  unspecifiability  of  complete  behavior  for
interactive   systems   is  a  computational   analog   of   Gödel
incompleteness for the integers.

Incompleteness  is a key to expressing richer behavior  shared  by
empirical  models of physics and the natural sciences. Interaction
machines have the behavioral power of empirical systems, providing
a  precise  characterization of empirical computer  science.  They
also   provide  a  precise  framework  for  object-based  software
engineering  and agent-oriented AI models that is more  expressive
than algorithmic models.

Fortunately the complete behavior of interaction machines  is  not
needed to harness their behavior for practical purposes. Interface
descriptions are the primary mechanism used by software  designers
and  application programmers for partially describing systems  for
the   purpose   of   designing,   controlling,   predicting,   and
understanding  them.  Interface descriptions  are  an  example  of
"harness constraints" that constrain interactive systems so  their
behavior  can  be harnessed for useful purposes. We  examine  both
system  constraints  like  transaction correctness  and  interface
constraints for software design and applications.



2.3 Robustness of interactive models

The  robustness of Turing machines in expressing the  behavior  of
algorithmic, functional, and logic languages has provided a  basis
for the development of a theory of computation as an extension  of
mathematics. Interaction machines are an equally robust  model  of
interactive  computation. Each concept on the  left-hand  side  of
figure  24  has  greater expressive power than  the  corresponding
concept  on the right-hand side. Moreover, it is conjectured  that
left-hand-side concepts have equivalent expressive power  captured
by  a  universal  interaction  machine,  just  as  right-hand-side
concepts  have  equivalent expressive power of  a  Turing  machine
(universal algorithm machine).

                 ... has richer behavior than ...

universal interaction machine     universal algorithm machine
interactive problem solving       algorithmic problem solving
open system                       closed computing system
programming in the large       >  programming in the small
object-based programming          procedure-oriented programming
distributed AI                    logic and search in AI
scientific modeling paradigm      mathematical reasoning paradigm
philosophical empiricism          philosophical rationalism

                  robust equivalence of behavior

 Figure 24: Parallel Robustness of Interaction and Turing Machines

Interaction machines provide a common modeling framework for left-
hand-side  concepts  just  as Turing  machines  provide  a  common
framework  for  right-hand-side concepts. The equivalence  of  the
first five right-hand-side entries is the basis for the robustness
of  Turing machines. The corresponding left-hand-side entries  are
less  familiar,  and  there has not until recently  been  a  crisp
notion  of expressive power for interactive problem solving,  open
systems, programming in the large, object-oriented programming, or
distributed artificial intelligence. Interaction machines  provide
a  crisp  model  for these concepts and allow the  equivalence  of
behavior  and of interactive problem-solving power to be expressed
as  computability  by  a  suitably-defined  universal  interaction

The  somewhat  fuzzy notion of programming in  the  large  can  be
precisely  defined  as  interactive  programming.  Large  entirely
algorithmic  programs of one million instructions do not  qualify,
while  modest interactive systems with a few thousand instructions
do.   The   identification  of  programming  in  the  large   with
interactive programming implies that programming in the  large  is
inherently nonalgorithmic, supporting the intuition of Fred Brooks
that  programming in the large is inherently complex.  Interaction
machines  provide a precise way of characterizing  fuzzy  concepts
like  programming in the large and empirical computer science  and
elevate the study of models for objects and software systems to  a
first-class status independent of the study of algorithms.

The  role  of  interaction machines in expressing the behavior  of
scientific models and empiricism is less direct than their role in
expressing open systems, object-based programming, and distributed
artificial intelligence. The identification of interactive problem
solving  with the scientific (empirical) modeling paradigm follows
from  the  correspondence  between interaction  and  observability
(interaction  from  the  point of  view  of  an  agent  or  server
corresponds to observability by an external client).

Interaction machines express processes of observation and  capture
the   intuitive  notion  of  empiricism.  Moreover,  the   logical
incompleteness of interaction machines corresponds to  descriptive
incompleteness   of   empirical  models.   Modeling   by   partial
description  of  interface behaviors is  normal  in  the  physical
sciences.  The  incompleteness of physical  models  is  forcefully
described by Plato in his parable of the cave, which asserts  that
humans  are  like  dwellers in a cave that can  observe  only  the
shadows  of reality on the walls of their cave but not the  actual
objects in the outside world.

Plato's pessimistic picture of empirical observation caused him to
deny  the validity of physical models and was responsible for  the
eclipse of empiricism for 2000 years. Modern empirical science  is
based  on the realization that partial descriptions (shadows)  are
sufficient  for  controlling, predicting,  and  understanding  the
objects  that  shadows represent. The representation  of  physical
phenomena by differential equations allows us to control, predict,
and even understand the phenomena represented without requiring  a
more  complete description of the phenomena. Similarly,  computing
systems  can be designed, controlled, and understood by interfaces
that  specify their desired behavior without completely accounting
for or describing their inner structure or all possible behavior.

Turing  machine models of computers correspond to Platonic  ideals
in  focusing  on  mathematical  tractability  at  the  expense  of
modeling accuracy. To realize logical completeness, they sacrifice
the  ability  to  model external interaction and  real  time.  The
extension  from Turing to interaction machines, and of  procedure-
oriented to object-based programming, is the computational  analog
of  the  liberation  of  the natural sciences  from  the  Platonic
worldview and the development of empirical science.

The correspondence of closed systems and philosophical rationalism
follows from Descartes' characterization of rationalism by "Cogito
ergo sum", which asserts that noninteractive thinking is the basis
for  existence and knowledge of the world. Interaction corresponds
precisely  to allowing internal computations (thinking  processes)
of agents (human or otherwise) to be influenced by observations of
an  external  environment. The correspondence between  rationalism
and empiricism and algorithmic and interactive computation is thus
quite  direct.  The demonstration that interaction  machines  have
richer behavior than Turing machines implies that empirical models
are  richer  than  rationalist models. Fuzzy questions  about  the
relation  between  rationalism  and  empiricism  can  be   crisply
formulated   and   settled  by  expressing  them   in   terms   of
computational models.

The equivalent expressive power of imperative (Turing machine) and
declarative   (first-order  logic)  models  lends  legitimacy   to
computer  science  as  a  robust  body  of  phenomena  with   many
equivalent models, including not only Turing machines but also the
predicate  and  lambda  calculus. Church's  thesis  expresses  the
prevailing  view  of  20th century formalists that  the  intuitive
notion  of  computing  is coextensive with the  formal  notion  of
functions computable by Turing machines. However, Church's  thesis
is  a  rationalist  illusion,  since Turing  machines  are  closed
systems  that shut out the world during the process of computation
and  can  very simply be extended to a richer intuitive notion  of
open,  interactive computation that more accurately expresses  the
interactive behavior of actual computers.

Declarative  and imperative systems compute results  from  axioms,
arguments  or  initial  inputs by rules  of  inference,  reduction
rules,  or  instructions.  The interactive  paradigm  extends  the
declarative   and   imperative  paradigms  by   allowing   initial
conditions  distributed over time. This extension is analogous  to
extending  differential  equation  techniques  from  one-point  to
distributed  boundary  conditions. In  a  distributed  interactive
system  we further extend initial conditions to distribution  over
both space and time. Distribution of initial conditions over space
is  familiar from multihead Turing machines and does not by itself
increase   expressive  power.  However,  distribution  over   time
increases expressive power:

declarative paradigm: initial conditions (axioms + theorem) +
                      rules of inference -> (yes + proof) or no
imperative paradigm:  initial value (precondition) and program
                      yields result (postcondition)
interactive paradigm: initial conditions distributed over space
                      and time, imperative or declarative rules

This  analysis suggests classifying paradigms by the  distribution
of  external  interactions over space and time. Differences  among
inner  rules  of  computation have no effect on expressive  power,
while  extension  from one-point to distributed  interaction  over
time increases expressive power. Interaction machines derive their
power  from their ability to harness the interactive power of  the
environment.  Their  expressive power is  comparable  to  that  of
managers who need not have inner ability to solve a problem  since
they can harness the problem-solving power of their employees.


Massimo Dentico