The robot pictured below has a transparent front and is
facing an (expandable) board, a little to its right, and a
mirror, a little
to its left.
It's transparent front enables it to see in the mirror its
complete underlying mechanism, flowchart, or program.
The board serves for input, output, and intermediate computations.
Such a self-referential or
self-reflecting robot has data access, then, to a
complete (low level) self model.
It is depicted
already having copied onto the board
a portion of its ``program'' (corrected for mirror reversal). Note that the
robot's self copy is projected externally
to the robot itself. In this way infinite
regress is not required for the robot
to have complete (low level) self
The use this robot makes of its complete (low level) self
whatever was built into it, but it could have been anything algorithmic.
For general computer programs, in contexts where mirrors may not be available,
a quiescent (low level) self-model can be obtained by a mechanism logically
similar to the self-replication mechanism employed by single-celled organisms.
See the second reference under
below or click
here for an brief essay of mine on the subject.
For more information on self-replication mechanisms, see
Page on Machine Self-Replication.
For connections to self-modification, see this
to the work of J-Paul Moulin.
I am interested in three aspects of machine self-reference.
(1) Its potential profound
philosophical importance as a model of perfect
knowledge. In Western philosophy, self
knowledge is thought to
Greg Riccardi's paper from his doctoral dissertation and
Jim Royer's doctoral dissertation, each
done under my direction and referenced just
below, for some preliminary
attempts to mathematically understand what use is self
knowledge. In these works machine self-reference is treated as a
(connotational) control structure. For example, the Royer reference presents
the result that, as control structures, neither self-reference
nor if-then-else can be built solely
from the other, but together they enable
the construction of any control structure: self-knowing and
decision-branching are complementary.
Computational Learning Theory page,
control structures are also mentioned --- click
to see the reference there.
For more recent attempts to understand mathematically the power of
machine self-knowledge, see my first two papers with Sam Moelius
see my NSF Nugget,
Theory of Program Self-Reflection.
of my papers below with Sam Moelius features applications of infinitary
machine self-reference for insight regarding computer virus detection.
(2) Its potential
practical importance in Artificial Intelligence.
theoretical applications, see the papers below and also those in:
theoretical application, as a tool, to provide succinct, elegant proofs
of results in theoretical computer science.
Historically, machine (or program)
self-reference started with the well-known mathematical
(see references just below).
Kleene's predecessor was the
mathematical logician of the century
who introduced the use
of self-referential sentences in formal languages of arithmetic.
I plan to write a paper revisiting
self-referential sentences, which paper will be
based on machine self-reference.
I also plan to write a paper, based on a new machine self-reference argument,
which will point toward the nicely controverisal
philosophical stance that human cognition is mechanistic. Regarding this
latter issue, see also my article
Encyclopedia of Artificial Intelligence, 2-nd edition (edited by S.
Shapiro), John Wiley and Sons, 1992.
In progress is
an article employing machine reference to the understanding
of the self-modeling component of human consciousness.
An expanded variant of the
conference slide version of this article is referenced
REPRESENTATIVE PUBLICATIONS (mentioned
A Note on Degrees of Self-Describing Turing Machines,
Journal of the Association for Computing
Machinery, 18 (1971), 329-338.
Periodicity in Generations of Automata,
Mathematical Systems Theory, 8 (1974), 15-32.
Infinitary Self Reference in Learning Theory,
Journal of Experimental and Theoretical Artificial
Intelligence, 6 (1994), 3-16.
Click here for Table of Contents and Chapter 1 of:
Subrecursive Programming Systems: Complexity &
J. Royer), research monograph
in the series Progress in Theoretical
Birkhauser Boston, 1994, 251pp, Hardcover $49.50,
ISBN 0-8176-3767-2, Phone: 1-800-777-4643,
Department Y807, P.O. Box 2485,
Secaucus, NJ 07096-2485 USA.
HERE for associated errata.
Machine Self Reference and Consciousness, presented at the
Third Annual Meeting of the Association for the
Scientific Study of Consciousness, London, Ontario, Canada,
June 4-7, 1999
For an expanded variant of the associated slides, click
Characterizing Programming Systems Allowing Program Self-Reference
, unexpanded version in S. B. Cooper, B. Löwe, and A. Sorbi, editors,
Computation and Logic in the Real World - Third Conference
of Computability in Europe (CiE 2007), Proceedings, volume
4497, Lecture Notes in Computer Science
pages 125-134, June 2007.
Properties Complementary to Program Self-Reference
S. Moelius), unexpanded version in
Proceedings of the 32nd International Symposium on
Mathematical Foundations of Computer Science 2007 (MFCS'07),
Lecture Notes in Computer Science Vol. 4708,
Springer-Verlag, Berlin, pages 253-263,
August 2007, to appear.
Cautious Virus Detection in the Extreme
S. Moelius), Proceedings of the 2007 ACM SIGPLAN Workshop on
Programming Languages and Analysis for Security (PLAS'07),
ACM, NY, NY, pages 47-51, June 2007.
May 29, 2013