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."

Snappy Comebacks

I'm currently training for my third marathon. I'm fortunate to have a place to run uninterrupted by cars, that is literally right out my front door. This makes it easy to stick to my training schedule. If you've ever trained for a marathon you know that it takes hundreds of miles of training for each one. If I stick to my exact schedule, I will run about 730 miles plus the race itself, from the start of training two months ago to November Fifth in New York City. Yes, I could just go out and run a few miles every week to stay in shape, but that wouldn't be nearly obsessive enough. It's all or nothing for me, so if I'm not training for a marathon or something, I'm lying around eating chips. I have done this a couple of other times, as well as running a half-ironman triathlon. My main observation from that is that a marathon makes a good warm-up for a half-ironman.

With a concrete bike path right out my front door, needless to say, many of those miles have been on that same path. Suffice it to say this ain't my first time around the block. Over time, I've learned things about this path. Like, it's pretty well maintained, and it's really busy on Saturdays. It meanders down along the length of a creek, crossing over it here and there on footbridges, and running up and down both sides of the creek in a loop for the most part. I also figured out that it doesn't really pay to alternate which way I run around the loop, because either way I end up running on the right edge of the path for the benefit of the many bicycles who also share the path. I don't begrudge them this; it is in fact a bicycle path. It's labeled as such on signs, and they don't say bicycle/jogging path or anything like that. As a matter of fact, when training for triathlons, I naturally used the bike path myself for its intended purpose. I also don't begrudge the many walkers who use this path their rights either, even though I have to run around them frequently, and their dogs crap incessantly on and off the path. I've gotten into such a habit of staying to the right that sometimes I even overdo it. If I see someone down the path a ways, I will often step off the path onto the grass due to some sort of weird mental gymnastics going on in my glucose-deprived brain. Even if no one is around, I have a bad habit of staying too far right and falling off the path from time to time; I worry that I will turn an ankle one of these days. I was always a geek in school, but the fact that both brain and muscles share the same supply of glucose sure goes a long way to explain why jocks were so dumb.

Anyway, enough background; on to the main story of the day. This morning, as I was heading out for a twelve mile long run (here under Basic Marathoner), I realized I better get going, because the local running club was having a 5k run on that very same path. While I do run with this group sometimes, I didn't want to this morning because the run was too short and it was too hot to wait around for them to start it. So, I wanted to be off the path when the race was run, because I hate getting in their way, so I usually end up running in the grass or avoiding them altogether if I'm not running the race. As such, I got an early start so I would be on the portion of the path they use before the race, and since I was doing two loops, I wouldn't be back on the path until the race was over. This worked out as expected. However, there were a lot of runners warming up before the race, so nevertheless the path was crowded with runners when I was down there, but the race wasn't on yet so I ran on the path.

I was coming up to one of the footbridges and there were a couple of people coming back the other way, and one guy ahead of me walking on the bridge. I pulled to the left to pass the walker, and just then, I saw a bicycle coming toward me at about twenty miles an hour, and there I was right smack in the middle of a footbridge that has rails going down both sides. The guy I was passing was to my right, so my only real choice was to dodge to the left. The bike saw me at about the same time and ground his brakes as he struggled to maintain only about 18 miles an hour through the pack of runners. The runners coming toward me had to kind of dodge around me and back toward him. Instead of apologizing, he growled "Walk Right!" as he goes by pissed that he is slowed to a mere 17 miles per hour. I shot back, "You run me off the road, and now you want to tell me which ditch I should jump into?" All the runners laughed, and the biker was so embarrassed, he got off and walked.

At least, that's what would have happened if I had been thinking faster (glucose again) and could have come up with that retort on the spot. As it was, it took me about twenty minutes to come up with. What I said instead was, "I wasn't walking, dumbass." I said it pretty quickly, but at his clip he didn't even hear me before he was long gone. And having said what I said just sounded stupid to the other runners, and especially the walker, who probably thought, "Then run right, dumbass." And I didn't come up with my retort until long after all the actors in this little drama were gone, so I still felt I should explain to someone. If I couln't rant to the cyclist, and I couldn't rant to all the other complete strangers, at least maybe some strangers will read it here. After all, what is a blog for, if not to get the last word?