Expressions that talk about themselves
Maarten M Fokkinga
Self-reference occurs frequently in theoretical investigations of formal
systems.
In Predicate Logic self-reference is used in G\"odels Incompleteness Theorem:
a formula is constructed that asserts ``I am not formally provable'';
in a programming language self-reference manifests itself in the existence of
a program that writes its own text, a so-called self-reproducing
program.
Also in Nature self-reference plays a role, in the ability of
self-reproduction of the formal system of DNA molecules.
Odifreddi~\cite[page 165--174]{odifreddi89} discusses these topics
and gives good references to the literature.
In this note we explain, independent of any formalism, how to construct an
expression in a formal system that ``does something with itself''.
As an application of this procedure we show how to construct a program that
writes its own text, lay-out included.
(Our self-reproducing Miranda script is, after some optimisation,
exactly 36 characters long!)
The full paper (postscript version): here (8 pages).
At present (Nov 1994) there are still some hard copies available.
Bibtex data
@article{mmf94b
,author = "Fokkinga, Maarten M."
,institution = "University of Twente"
,title = "Expressions that talk about themselves"
,journal = "The Computer Journal"
,year = "1996"
,number = "5"
,pages = "408--412"
,comment = "Previous version: Memoranda Informatica, Nr 94-29, June 1994."
}