This

This post refers to itself (but since I wrote it, blogspot has disabled such links). For a long time, since I have been a student of Computer Science, I have found the topic of self-reference and the implications it leads to, fascinating. One of the early mathematicians to deal with the problem of self-reference was Bertrand Russell. He looked at the collection of sets that do not contain themselves in naive set theory. What he found is that there was no reason that such a collection cannot itself define a set. So then the question arises as to whether it contains itself or not. Because if it does, then it shouldn't, but if it doesn't, then it should. A variant of this idea is that there is a (male) barber in a town who shaves all and only those men who do not shave themselves. Does he shave himself, or not? Perhaps he grows a beard.The barber's paradox can be laughed off as a joke, claiming that no such barber can exist by definition. Russell's paradox proved a little more tricky. All kinds of restrictions were put into place on the definition of sets and what they could contain. New theories sprouted, and a new ZMF set theory was created and canonicalized. No, not canonized, that would mean attaining sainthood.

However, the forces of evil went undeterred. The smart-alec mathematicican Kurt Goedel went on to show something quite remarkable and inescapable. First he showed that since all theorems of mathematics are finite, they can be described as a string of symbols, which can be converted to a unique integer number. This fact doesn't surprise us now, in the age of computers where everything is a binary number, but back then it seemed like a big deal. You may think of your hard drive as a collection of files, but in fact it is one long string of bits, representing a ginormous integer. In any event, even the hypothetical theorem, "This is not a theorem of mathematics" can be expressed as an integer. Note the self-reference. Now, all we have to do is prove or disprove that theorem. After all, if theorems are finite, and their proofs are finite, all we have to do is try all possible proofs until we prove or disprove it. If we prove it, then it actually is a theorem of mathematics, because it can be proven. If we disprove it, then it is in fact true that it is not a theorem of mathematics, and it can be stated categorically that it is not. But such a statement is the statement itself. So we either have a theorem which can be proven, but which is false, or we have a theorem which cannot be proven, but is nonetheless true. It all depends on what we pick for axioms. So for any formal system which allows for the use of integers, we have either inconsistency built-in, or incompleteness built-in. And there's no way within that system to know which it is. Every now and then some misinformed joker comes up with a claimed "proof" that shows ZMF set theory to be inconsistent by proving and disproving the same statement, but so far all the proofs have been flawed (more likely laughable).

Computer science was somewhat birthed by this notion of self-identification, numeric representation of mathematical symbols, and computability. Before computers were invented, Alan Turing asked what it was that could be computed. He was really just trying to simplify the aspects of what it was that mathematicians did when he invented the concept now known as the Turing machine. He envisioned a machine that could be instructed to do mathematical work, which he saw as consisting of reading symbols off of paper, which he simplified to a linear list of paper, and then writing things back onto paper. Of course the mathematician has to follow the rules of mathematics, which he generalized to be a set of rules that the machine followed when it encountered any given symbol, and those symbols could cause the machine to enter a new state, where it would follow new rules, until it was complete. But the real breakthrough came when he realized that what he was doing was itself mathematical work. So, a Turing machine could be described by a set of symbols that described states, symbols to read, symbols to write, and when to do what. Finally, a Universal Turing Machine (UTM) could be described which would know how to read a description of a Turing machine, along with its input, and simulate that Turing machine on that input. I think you can see where this is going. Clearly the UTM could work on itself.

So, now Turing thought to ask the question: Can a Turing machine be created that can tell if another Turing machine will stop? Seems like a simple question; some TM's run in loops forever, and some don't, so I want some way to know which are which automatically. Of course, this led back to our old friend Goedel, because a TM is, after all, a formal system with a sort of set of "axioms", and could be used to prove theorems if it were instructed to do so. TMs, which are similar to Programs, of course, can be represented as numbers, as they are every day, and hence can be fed to themselves. Turing just had to feed the hypothetical halting program back into the UTM to ask the question: "IF I halt, loop forever, else halt." If a halting program existed, then the quoted program could just call it with itself as input and it could not possibly produce a valid answer. Thus it was discovered that not everything can be computed. There are many equivalent problems in computer science that have since been shown to be uncomputable.

Douglas Hofstadter once wrote a book called "Goedel, Escher, Bach", with far more umlauts that I have used, in which he expounded on this and related topics. I'm sure that his book, like my post, refers to itself somewhere. For the 20th anniversary of that book, the only thing he changed was to write a forward lamenting that most people had missed the central theme of his book, which was about self and self-reference. I seem to remember also that he was concerned that the hippies had somewhat misinterpreted his work as supporting the post-modern perception that there are no absolutes and whatnot, but in my view, you can't write worrying about what the hippies will think. They're already off the deep end, no turning back now.

Anyway, speaking of writing, I was once put in the position, with alcohol involved, of trying to decide what to get for a tattoo. I had honestly never thought about it before, and that kind of turned out to be the deal-breaker. I didn't want anything cliched or off the wall (literally), I was looking more for something off-the-wall. I thought about getting an Ironman logo, since I had done a half-ironman, but that seemed like a half-baked idea. Later, I came up with the idea of getting the word "this" tattooed on my arm. That way, when someone asked what it was, I could respond, "It's a tattoo of itself."