self-reference in computation

Self-reference is the act of a program talking about, or being fed, its own description. It sounds exotic, but it is everyday: a compiler is a program that processes programs, an antivirus scans executables, and a quine is a program that prints its own source code. The startling power of the halting proof comes from letting a program ask a question about ITSELF and then react to the answer. This loop-back is what turns an innocent assumption into a contradiction.

Why is self-reference possible at all? Because programs are just strings of symbols, and a string can be handed to another program as ordinary data. So there is no obstacle to running machine M with the code of M itself as input — written (M, M). This is the move at the heart of diagonalization: we build a machine D that consults a supposed halt-decider about D-on-D, then deliberately contradicts the prediction. The machine is reasoning about its own future behaviour and then sabotaging it. The recursion theorem later makes this rigorous, guaranteeing that any machine can obtain and use its own description.

The same pattern recurs throughout logic and computer science: Cantor's diagonal sequence differs from itself-as-listed, Godel's incompleteness sentence says 'I am not provable', and the liar sentence says 'I am false'. In each case a system is rich enough to describe its own statements, and that very richness lets us build a self-referential object that no consistent answer can pin down. The lesson for a programmer is humbling: precisely because our languages are powerful enough to manipulate code as data, they are powerful enough to pose questions about themselves that no program can settle.