MaCro Philosophy
12-October-2017

Strange Loops Part 1: What is a Strange Loop?

Douglas Hofstadter thinks you are a strange loop. I think he's right. Unfortunately, the two best examples of strange loops are Gödel's incompleteness theorem and the human brain, neither of which is particularly easy to understand. In this post I break down the key components of strange loops (without too much logic). In the following weeks I will cover the ways in which we are strange loops, and how we can use modern AI to build them.

Plain Old Loops

A plain old loop. Warning: might be loud.

It is obvious what a loop is. A ring is a loop. Projecting a video camera onto a screen and then pointing the camera at the screen makes a loop. Loops are interesting because they can capture infinity in a finite space. But beyond that are not all that special by themselves.

Weird Loops

The Penrose steps, a weird loop (Inception version).

Some loops, such as the Penrose steps (right), or Shepard tone (below), are a bit weirder. They loop back on themselves in seemingly impossible ways. But the paradoxes are often explained away as illusions. These don't yet qualify as strange loops.

The Shepard tone sounds like it is constantly rising.

Hierarchical Loops

A hierarchical loop. M.C. Escher

Creeping up on strangeness, we have loops in which (in Hofstadter's words) "there is a shift from one level of abstraction (or structure) to another, which feels like an upwards movement in a hierarchy" [I am a strange loop. pp.101-102]. In the case of Escher's Drawing Hands, we have low-level ink marks on a page becoming real hands (a higher-level concept), capable themselves of drawing the low-level ink marks on the page. The jump up a hierarchical level from ink marks to hands is necessary to complete the loop because hands are needed to draw. Ink marks themselves cannot draw anything.

Hofstadter laments, if only the hands were real! This would be a perfect example of a strange loop. Instead, the illusion is shattered when we realise that the high-level interpretation (drawing hands) are in reality nothing more than ink marks on the page themselves.

Self Referencing Hierarchical Loops

Oddly, Hofstadter does not put too much emphasis on the self reference part. Presumably this because, to him, self reference is obvious and is already implicit in the notion of a low-level system becoming a high-level system and then looping back on itself. However, it is important to spend some time here. When we look closely we find that there are, in fact, two distinct types of self reference involved in Gödel's proof, our prime example of a strange loop. Fortunately, we only need a basic overview to see what kind of self reference is required and can avoid the more complicated parts.1

Brief Logical Interlude

At the core of a logical system are a finite set of symbols that can be combined together to make sentences. For example, a logical system for simple arithmetic may contain the symbols '0123456789+-x/='. The system also contains rules for combining the symbols to form valid sentences. For example, in the system designed for arithmetic, the rules might produce the sentence 212x123=28076, which would be valid. However, it would not be able to produce the sentence '==//x-', even though it contains all of the right symbols.

To make it interesting, we want to know which of the valid sentences are true and which are false. Does 212x123 actually equal 28076? To do this the system also has a small set of sentences that we take to be self-evidently true (such as '0+1=1'), and that are used as starting points for proofs. It also contains a set of rules that can be applied to combine true sentences (such as the starting sentences) into more and more complex sentences that are also true. A proof begins with the starting sentences and keeps applying the rules until it gets to the target sentence. Each possible combination of starting sentences and rules is a proof. There are infinitely many of these as the rules can be applied repeatedly. We agree the starting sentences are self-evidently true, and the rules turn true sentences into more complex true sentences. If we get to the target sentence using the rules, we can therefore conclude that it is also true.

Obviously, we need to make sure that the rules and the starting points are designed so that they don't ever lead to any false sentences (like 212x123=28076). If so, then the system is consistent. Further, if a sentence is true, then we want it to be possible to prove the sentence using the rules. If this is possible for all true sentences, then the system is complete. Gödel showed that any consistent logical system of sufficient complexity must contain a sentence that is true, but for which there is no proof (i.e. it must be incomplete).

Gödel's Proof

The proof works by constructing a sentence that basically says:

There is no possible proof of this sentence.

We know that this sentence must be true in a consistent system. If it were false, there would be a proof of it, and a proof of a false sentence means that the system is inconsistent. However, given that the sentence is true, then the system must be incomplete. The sentence is an example of a true sentence that has no proof. Any system in which you can construct this sentence must be incomplete.

The real trick of Gödel's proof is not coming up with this paradoxical sentence, but showing exactly how it can be constructed in certain logical systems. This involves a complicated labelling system that requires what Hofstadter calls an upwards shift in a hierarchy. Fortunately, we do not need to worry about any of the technical details of how this is done. It is possible to see just from the structure of the sentence what kind of self-reference is involved.

Self-Reference 1: The Unified Infinite System

This is the simpler type of self-reference and concerns the part "There is no possible proof". To show that no proof exists involves considering the infinite set of all possible proofs, and showing that none of them are proofs of the sentence in question. This requires the ability to refer to an infinite set in a finite sentence. This itself requires an upward shift in hierarchy.

To use language that will also be applicable to the human case, the upward shift in hierarchy must allow for reasoning over all possibilities of the system. This is self-reference where the system as a whole is considered as a single entity to be reasoned over. To skip ahead a bit, this corresponds to the commonly accepted unified nature of consciousness.

Self-Reference 2: A Component Itself

The second part is the trickier type and concerns "of this sentence". In this case the self that is being referenced is the very sentence under consideration. This page contains a list of programs, for many different programming languages, that can output themselves. A quick attempt (even ignoring problems with quotation marks) shows us the difficulty.

PROGRAM: print "print"
OUTPUT: print
But that only prints out the print command, not the whole program, so how about:
PROGRAM: print "print "print""
OUTPUT: print "print"
This doesn't work. Extending the string to be printed extends the program itself, leading to an infinite regress. A common successful technique is to define a variable that contains a string to output, and call it using a built in method that replaces key parts of the string.

To make matters worse, in Gödel's proof, the sentence that references itself must also contain a reference to the infinite system as a whole (self-reference type 1). Again, we are not concerned here with explaining exactly how this is achieved, just with identifying that it is an important part of the quintessential strange loop. To use language that will also be applicable to the human case, the upward shift in hierarchy must allow for certain individual elements of the system to be about themselves.

Closing the Loop

Of course, this is only interesting because the shift up in hierarchy allows us to conclude properties about the low-level system (in this case its incompleteness), therefore closing the loop.

Conclusion

We have finally covered all the components of strange loops. They must:

In part 2 I cover the ways in which we are strange loops.

In part 3 I will cover how, with current AI technology, we can build them.

Footnotes

1. For those interested, the clearest short summary of the proof I've read can be found in the third answer, by Mark Dominus, on this stackexchange thread, which influenced my attempt at a basic overview. For a complete account, I have found Raymond Smullyan's book to be the most accessible.