Recent News
Computer science student navigates crime’s depths with AI at Department of Homeland Security internship
August 25, 2023
UNM researchers take a deep dive into our changing planet with SIMReef project
August 1, 2023
Dongarra elected into the National Academy of Sciences
June 28, 2023
UNM receives $1.5 million to support computational workforce development
May 8, 2023
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.