I've found myself peering into a number of different computer sciencey books (though I am also coming to realize that "I've never liked the term 'computer science,'" Hackers and Painters par. 4) in the past few weeks: The Unix Programming Environment, Gödel's Proof, Proving Darwin: Making Biology Mathematical (bad title), and Gödel Escher Bach.1

Formal logic was something that really piqued my interest in high school but I never took that class in mathematical logic and never really developed the rigor for appreciating Gödel's Incompleteness Theorem. I have really enjoyed Nagel's exposition in Gödel's Proof for its selective depth and rigor. High quality laymen's books are really a pleasure!

I've known about Principia Mathematica for a while, I even attended one of Saul Kripke's lectures on the book at the CUNY graduate center in New York City, but I never really "got it." I don't think I could appreciate the idea of a complete axiomatic system (for all of number theory and perhaps all of mathematics) without having done some programming. The concept that I've come to appreciate is that of a logical system of inference which is technically devoid of all meaning. Technically devoid of meaning in the sense that one (man or machine) does not need to know anything outside of the system in order to exercise some technique on it, that is, to manipulate and create new statements.

So what an axiomatic deductive system amounts to is a list of characters (or strings, some or other material), and some rules for how to generate other lists of characters from the original list of characters. Those characters could be English words, or they could be the symbols in basic arithmetic. You could sit down and write a computer program that would (given infinite time) iterate through every single deducible statement. Furthermore, the choice of symbols is completely arbitrary. The computer doesn't care what these symbols signify. If we had a program that printed out all of the statements of arithemetic, we could exchange the + and = symbols and nothing would fundamentally would change, except for the fact that we would really have to squint at the printout to make any sense of it.

I picked up The Unix Programming Environment yesterday and was just paging through it when I got to Chapter 8, Program Development in which K&P work through the development of a simple but powerful programming language using yacc and lex. If only I had appreciated the gems in this book a few years ago when I was taking a course that featured the book, but enough of that. In this framework (and I'm not sure if there are others) writing a computer language amounts to doing two things, which conveniently match up to the two tools being used, yacc and lex. Lex takes input from the outside world and turns it into symbols (tokens) that yacc can understand. Let's look at yacc at itself doing two things. The first is that it defines a grammar in the sense that we are discussing above with Principia Mathematica, a set of inference rules for how to get from one string of symbols to another. The second is that it defines what to do with those statements. You literally write exactly what the computer should do if it sees a particular type of statement. When you do this, you are giving the grammar meaning.

Now let's return to English and arithemtic. There seems to be a fundamental difference because every valid string in arithemetic is meaningful, but not so with every grammatically valid string in English (Chomsky's famous, "colorless green ideas sleep furiously," actually my friend, Noam Faust, who studies these sorts of things for a living, first told me about this). What is it that makes this not meaningful? I would argue that it is because there is somehow nothing to do with the statement, there is no action to be taken. Who cares? Not sure, this really may be intellectual masturbation. But, now returning to lex and yacc, it is interesting to think that what makes the language meaningful is action, the computer knowing what to run along and do when it sees such and such a statement. Under the hood, I have Wittgenstein's Philosophical Investigations in mind (another book from college) in which Wittgenstein discusses the meaning of language as behavior and action. His thought process is scientific: if it weren't for some sort of behavior or action, how would we ever know that someone understood what we were talking about?

And finally, I have to bring up a quote from Gödel Escher Bach:

...if the sequence of bases which compose a strand of DNA were sent as abstract symbols, not as a long helical molecule, the odds are virtually nil that this, as an outer message, would trigger the proper decoding mechanism which would enable the phenotype to be drawn out of the genotype. This would be a case of wrapping an inner message in such an abstract outer message that the context-restoring power of the outer message would be lost, and so in a very pragmatic sense, the set of symbols would have no intrinsic meaning. Lest you think this all sounds hopelessly abstract and philosophical, consider that the exact moment when phenotype can be said to be "available", or "implied", by genotype, is a highly charged issue in our day: it is the issue of abortion.

Douglas Hofstadter, Gödel Escher Bach p.184

When thinking about computing mechanisms in nature, and this where I am at right now when it comes to biology, things become much different. It would seems like any string of As, Cs, Gs, and Ts are valid, but that only calls into question our simple and predefined notions of validity. Perhaps the rules are more similar to human language than computer languages (as they exist today). In any case, the meaning of a string of nucleotide bases, what they actually do, is something entirely different than the string itself. And now that I've made a gesture toward tying all this back to biology, if only very abstract biology, I'll say goodbye for now.

[1] The first book was given to me in a college course. The second and third I ran into recently at my college bookstore, feeling nostalgic, I couldn't resist buying them. So there you go about the importance and influence of a college education, though I hesitate to say that it is for everyone.