Sridhar Vembu’s Blog

I have lately been educating myself on the foundations of Computer Science. I come from a more physical engineering background, with a strong dose of mathematical modeling, which in engineering is governed by experimental verifiability as well as analytical tractability.

With that background, it seems to me that theory of computing can be approached in two distinct ways. Though the two approaches are equivalent, they lead to different insights, and different kinds of programming languages.

For an engineer, the more familiar approach is the Turing Machine (by the mathematician Alan Turing), as the model of a computer program. This machine consists of an infinitely long tape with a read/write head, and a state machine that drives the read/write head.

For the mathematician, the preferred model seems to be the Lambda Calculus, invented by Alonzo Church. It deals with mathematical functions and recursion.

The most amazing thing, suggestive of the wave/particle duality in Quantum Mechanics, is that these two models have equivalent computing power: i.e you can represent any computer program in either of the two models. In fact, the famous Church Thesis postulates that there is a universal computing model, and the Turing Machine (or equivalently the Lambda Calculus) represents that ultimate computing model.

Roughly speaking, programming langauges like C or even Java, called “imperative languages”, are remotely (very remotely!) evocative of the Turing model, while “functional languages” like Lisp or Scheme are (somewhat more closely) evocative of the Church model. Most languages, including the four mentioned above, mix the two perspectives, so it is really a matter of degree.

As an engineer, I personally find imperative languages much easier to understand and use. Judging by their popularity, that seems to be a common feeling. Yet, there exist purists, mostly from the “functional” camp, who suggest that such a preference is somehow indicative of a lower IQ, under the assumption that anything that is popular must be of low quality. You can see this line of argument in the Lisp community.

The imperative vs functional perspectives can be compared with the Physicist vs Mathematician arguments I have heard in college. Physicists are the logical precursors to engineers, while mathematicians are the ancestors of pure computer scientists. Mathematicians will charge that physicists rely on intuition too much, and lack mathematical rigor, while physicists will charge mathematicians with abstraction for its own sake.

Which one is “right”? I suppose it is really a matter of personal taste. My experience is that human intuition comes first, and then the mathematical rigor. I don’t know of anyone who can write down formally constructed mathematical proofs out of thin air - I am sure they exist but I haven’t met them. Physical intuition is fallible, but that is the only weapon we have.

And then there is Godel, the ultimate weapon that physicists have against the mathematicians - a subject for another day.