A mathematical foundation of reflexion?

Massimo Dentico m.dentico@teseo.it
Fri, 07 Jan 2000 02:42:21 +0100

>From "Draft of ECOOP ‘99 Banquet Speech", Peter Wegner


There  is  abundant evidence that interactive services  over  time
cannot be expressed by algorithms, but this result is difficult to
prove  theoretically. My colleague Dina Goldin and I have  pursued
two  principal approaches towards this end, by machine models  and
mathematical  models.  Persistent Turing machines  are  a  minimal
extension of Turing machines that express interactive behavior  by
multi-tape  machines with a persistent worktape preserved  between
interactions.   Non-well-founded  sets   are   an   extension   of
traditional sets that provide a mathematical model of streams  and
interactive   computing  in  terms  of  circular  reasoning.   The
**mathematics of circular reasoning** was discovered only  in  the
1980s and is comprehensively presented for the fitrst time in  the
1995  book Vicious Circles by Barwise and Moss. I will not try  to
explain non-well-founded set theory in a banquet speech, but  will
say  a  little  about  the  intuitions  that  underlie  **circular
reasoning**  and  the  reasons that  it  was  not  discovered  and
developed earlier.

The  key intuition is that the class of things that a finite agent
can  observe is greater than the class of things that an agent can
construct.  We  can formalize this intuition by  showng  that  the
class  of things that an agent can construct is enumerable,  while
the  set  of situation that an agent can observe is nonenumerable.
Moreover, we can show that constructible sets can be specified  by
induction, while observable sets require a stronger inference rule
called coinduction.

Bertrand  Russell in the 1900s and Hilbert and Godel in the  1920s
made a fundamental mathematical mistake in assuming that induction
was  the  strongest  form of definition and reasoning.  They  were
misled  by the paradoxes of set theory and mitskenly thought  that
**circular  reasoning** needed to describe  observation  processes
was  inconsistent. In fact, **circular reasoning**  is  consistent
and  allows  stronger  forms of definiton and  reasoning  than  is
possible  through  induction. Though induction  is  sufficient  to
describe  construction processes stronger forms of  reasoning  are
needed to express observation processes. Turing machines turn  out
to  be  the  strongest form of computation possible  by  inductive
reasoning  but  are  not  strong  enough  to  express  interactive
computations  of finite agents that observe an incompletely  known
environment, which are modeled by **circular reasoning**.


See also: "Interaction, Computability, and Church’s Thesis", Peter
Wegner, Dina Goldin, chapter 3. Mathematical Models of Interaction

Massimo Dentico