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
(http://www.cs.brown.edu/people/pw/papers/ecoop99_speech.pdf)
------------------------------------------------------------------
[...]
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
(http://www.cs.brown.edu/people/pw/papers/bcj1.pdf)
--
Massimo Dentico