News Archives

Self-Reference in Computer Science

June 22, 2005

  • Date: Wednesday, June 22, 2005 
  • Time: 11:00 a.m.
  •  Place: FEC 141

Professor Neil D. Jones
DIKU (Computer Science Department) University of Copenhagen

This overview talk describes several forms of self-reference in Computer Science, all having to do with programming languages. The foundations of Computer Science stem from Recursive Function Theory in Mathematics, which as starting postulates three assumptions about any algorithmic language L:

1. L has a self-interpreter (also called a “universal function”)

2. L-programs can be specialized (Kleene’s S-m-n Theorem, or “partial evaluation”)

3. Computational completeness: a function is L-computable if and only if it is computable by some Turing machine.

Both 1 and 2 are (or can be) self-referential by nature: a self-interpreter may be applied to interpret itself, and a specializer may be used to specialize itself.

- The first leads to the well-known unsolvability of the Halting Problem.

- The second leads to practically usable methods for compiling, given an interpreter, and even to automatic generation of compilers from interpreters. Reference: Partial Evaluation and Automatic Program Generation, Jones, Gomard and Sestoft, 1993.

- A combination of the two leads to Kleene’s fascinating Second Recursion Theorem that, in effect, states that any programming language allows the use of “reflective” programs that are allowed to refer to their own texts in order to carry out a computation.