This entry is about self-reference, so (inevitably), it refers to itself. Sometimes individual sentences in it refer to themselves, like this one. This sentence refers to the futility of expecting a self-referential entry to refrain from referring to itself. Sometimes gratuitously. This sentence attempts to finish off this paragraph (which is rapidly becoming silly) and get on with the entry, but fails. This one however, succeeds.

Self-reference in Language

The first recognised instance of self-reference was the statement of Epimenides (7th Century BC) that 'All Cretans are liars'. Epimenides was himself from Crete. This statement (with a slight modification and simplification to 'This sentence is false') is now known as The Liar's Paradox, and self-reference has been linked with paradox ever since.

However, self-reference need not be paradoxical. We use self-reference in normal speech every time we use the word 'I', or even 'word', 'sentence', or 'language'. As an illustration, consider the statement 'Clean me!' written with a finger in the dirt on the back of countless vans and buses. What does this mean?

The options include:

• The bus expressing its wish to be cleaned.

• Whoever wrote it wanting to be cleaned (presumably having just been splashed by the bus driving through a puddle).

• The dirt itself wanting to be cleaned off the bus.

• The badly phrased, impolite sentence 'Clean me!' wanting to be cleaned up to something like 'I desire to be cleaned'.

There is an awful lot hidden behind words such as 'me', 'I', or 'this', when they are taken in a self-referential manner. We are used to processing all of the hidden stuff automatically, since we use the words so often. Some examples of self-referential sentences from Douglas Hofstadter's Metamagical Themas¹:

• This sentence no verb.

• Thit sentence is not self-referential because 'thit' is not a word.

• No language can express every thought unambiguously, least of all this one.

• a preposition. This sentence ends in

• This sentence every third, but it still comprehensible.

• This line from Shakespeare has delusions of grandeur.

• The rest of this sentence is written in Thailand, on

• This sentence does in fact not have the property it claims not to have.

• It always takes longer than you think it will take, even if you take into account Hofstadter's Law.

The last sentence in that list is, of course, Hofstadter's Law. This is an example of an endless loop, a not uncommon effect of self-reference.

Self-reference in Art

Magritte

René Magritte used self-reference in his painting The Betrayal of Images (1928). The painting consists of a side view of a smoking pipe, with the words 'Ceci n'est pas une pipe' (This is not a pipe) written below. Again, the 'Ceci' ('this') could refer to a number of things. Referring to the painting itself, the statement is true, it's a painting of a pipe (with some words underneath it - or 'Ceci' might refer only to the part of the painting concerning the pipe), not an actual pipe. It could also refer to the original actual pipe that was painted, Magritte's point (presumably) being that the image is not the object itself.

Escher

Escher used self-reference in much of his work. Drawing Hands (1948) shows a notepad, with a hand drawing (with a pencil) the shirt cuff of an arm that ends in a hand drawing (with a pencil) the shirt cuff of an arm that ends in the first hand. One hand is drawing the other, which is drawing the first. Were we to see simply a hand drawing another hand, it would still be self-referential, (in a weaker sense) but the picture would not be paradoxical - the paradox comes from the two-stage loop of references, each reference being 'is drawing'. Closing the loop even tighter is Print Gallery (1956). In the bottom left of the picture, a young man standing in a print gallery looks at a painting of a ship steaming into harbour, the harbour merging into a town, with many close-packed buildings. A woman looks out of the first floor window of one of the buildings, the ground floor consisting of a print gallery, in which the young man is standing. The picture refers to itself by being inside of itself.

Self-reference in Computers

It is said that when programming computers you are creating things from 'pure mindstuff' - building temples out of the air. It is, perhaps, no surprise that programs can contain self-reference.

Recursive Functions

A recursive function is a function that calls itself in order to return an answer - the classic example is factorials: in order to calculate 5!, simply deduce 4! and multiply it by 5. In general, we can write fact(x) = x times fact(x-1). This is self-reference because a function is defined in terms of itself.

Recursion avoids an endless loop when it doesn't quite refer back to exactly the same place. In the above example, fact(x) refers to fact(x-1), but if it had referred to fact(x) itself, we would be in trouble. This would be a case of a 'circular definition' (also to be avoided in mathematics). Less obvious cases of circular definitions can involve more than one thing, eg we might define A in terms of B, and B in terms of A. Just looking at the definition of A alone, it all looks fine, until we try to find out what we're talking about and find our castle in the sky hasn't got any foundations. Recursion also requires that it 'bottoms out' at some point. In the factorials example, it bottoms out by defining 0! = 1. If we didn't specify a 'fixed point' then to find 0! we would first try to find (-1)!, for which we need to find (-2)!, for which we need to find (-3)!, ... another example of an endless loop.

Because recursion is self-reference it is very powerful from a theoretical point of view: having recursion in a language automatically makes it 'Turing complete' which makes it capable of as many things as any other language, but also makes it suffer from the halting problem and similar things.

Reflection

If recursion is the practice of calling your own code, then reflection is the practice of looking at your own code. This is most often used in Object Orientated Languages, such as java. In such a language we can instruct a computer to 'know thyself'.

For example, suppose we want to create some code which will create new instances of any object we pass it - so if we pass it a Mercedes it will spit out another Mercedes. This process of 'cloning' requires reflection so we can find out everything there is to know about the passed object, without initially knowing what it is.

Normally reflection is only permitted at a fairly high level: we have access to what chunks of code there are, but not what each individual line is. This is largely because it does not seem to be useful - artificial intelligence has a long way to go before computers can make sense of human-written code in a useful way.

Self-modifying Code

Finally, self-modifying code is code which can modify its own code, which is the most powerful (and also by far the most complicated) ability yet. Self-modifying code can effectively redefine itself and what it does on the fly - here's an example:

Suppose you have a function which will return the number of times it has been called. Normally such a function would look something like this:

int count = 0;
int counter() {
count = count + 1;
return count;
}

Using self-modifying code, it would look something like the following:

line 1 - int counter() {
line 2 - *SELF-MODIFY*: add one to the integer in line 3
line 3 - return 0;
line 4 - }

In the past, self-modifying code has been the preserve of those who wrote directly in machine code - and even those hardy fellows treated it with the respect that it deserved. Why use it if it's so dangerous? Simple: it's fast - and there are some cases when it's worth spending twice the normal time coding to get that speed.

Nowadays, very few people program in machine code, so it is much, much, less of an issue. However, there are cases where it still occurs. The first is in games like 'Core War' - where pieces of code are created which do battle against each other - typically winning by causing the opposing program to execute an illegal instruction. The best programs in these games are invariably self-modifying. The second is simply by mistake: if a program has a bug and starts randomly corrupting memory, some of the corrupted memory may turn out to be its own code. When this happens, all bets are off. The third is in evolution research. Typically, a bunch of programs are let loose in some virtual playground, where death and radiation randomly cull and mutate, respectively, the inhabitants. Just as in natural selection, the programs which are alive at the end are the 'fittest' - being able to reproduce faster and more accurately than their forefathers.

Finally, some programming languages allow programs to create new pieces of code, compile them, and then create objects according to the newly compiled blueprint. Misused, this is almost as unstable as the original machine code self-modification, but it does have its uses, for example in writing sophisticated programming tools, and in certain brands of AI.

Self-reference in Mathematics

Russell's Paradox

Mathematics has a slightly uneasy relationship with self-reference, due to its propensity to produce paradoxes, the most famous example being Russell's Paradox (discovered by Bertrand Russell in 1901 while working on his Principles of Mathematics). The basic idea is summed up in the Barber Paradox:

In a small town, a barber cuts the hair of all people who do not cut their own hair, and does not cut the hair of people who cut their own hair. Does the barber cut his own hair? Suppose he does cut his own hair. But by the second half of the first sentence, he doesn't cut the hair of people who cut their own hair, including the barber himself. Contradiction. Suppose he doesn't cut his own hair. Then by the first half of the first sentence he does cut the hair of people who don't cut their own, including the barber himself. Contradiction.

Now replace 'people' with 'sets', and 'cuts the hair of' with 'contains' to get Russell's Paradox:

Consider the set B, which is the set that contains all sets that do not contain themselves and does not contain any sets that do contain themselves. Does B contain itself? Suppose it does contain itself. But by the second half of the first sentence, it doesn't contain sets that contain themselves, including B itself. Contradiction. Suppose it doesn't contain itself. Then by the first half of the first sentence it contains all sets that include themselves, including B itself. Contradiction.

This paradox caused an awful lot of trouble at the time. It seemed that the most basic foundations of mathematics (you can't get much more basic than sets of things) had contradictions in them. And in mathematics, once you've got a contradiction in a system, you can prove anything and everything. The paradox works because it is able to refer to itself (albeit indirectly) in its statement.

This self-reference is avoided today by restricting the definition of what a 'set' can be, essentially to cut out any possibility that it might contain itself.

Gödel's Incompleteness Theorem

Self-reference isn't all bad news for mathematics though. Possibly the most important result in metamathematics (mathematics talking about mathematics), Gödel's Incompleteness Theorem (Kurt Gödel, 1931) uses it. The theorem basically tells us that given any consistent system of mathematics complicated enough to do basic arithmetic, we can find statements which are true, but cannot be proved to be true (or false) within that system. The key idea of the proof is to get a statement to refer to itself (self-reference), essentially saying 'This statement cannot be proved in system X', where X is the system we start with. Then the statement is true, using reasoning from outside the system (if you could prove the statement in the system, then it would contradict itself, so you must not be able to do so, so what the statement claims is true), but you cannot prove that it is true from inside the system. The hard bit of the proof is getting the statement to refer to itself rigorously.

Of course, no entry on self-reference would be complete without a self-referential concluding paragraph², such as this rather apt paragraph itself. Though we really need a self-referential final sentence to finish it off. Unlike the previous sentence which wasn't very self-referential, not being the final sentence of the entry. That one wouldn't do either, since it refers to the sentence before it, rather than itself. As does that one. And that. You get the idea. This.