Church's Conjecture

In computer science there is a fundamental theorem that can be viewed as, in many ways, being just the opposite of the Sapir-Whorf hypothesis.

Back in the 1930's there was a great deal of theoretical work on different models of computation. In time many of these were shown to have the same theoretical power, in the sense that either one could simulate the other. This led to a conjucture that we now know as Church's Conjecture.

Church's conjecture says that anything that can ever be computed can be computed by a Turing machine. Turing machines are wonderfully simple devices, so this is at first a somewhat surprizing statement.

Of course, this is a statement of theory. Rather akin to the assertion that with time and effort and careful study I could learn to look at a field of snow and see exactly what the Eskimo sees, even if my language is English. It does not say that it is easy.

The late Alan Perlis used to use the phrase ``Turing Tarpit'' to mean the argument that my language can simulate your language, and therefore has more power than does yours. The tarpit is that in a theoretical sense all languages have exactly the same power, the power of a Turing machine.

The question is not what is possible, but what is easy. And it is here that languages clearly differ. Would you, for example, want to write an event-driven GUI interface using a Turing Machine? Probably not.

Object-oriented languages are important because they make it easy to think about the world in an object-oriented way. This doesn't imply either than one must program in an object-oriented way when using an object-oriented language, Tony Hoare has quipped that ``one can write FORTRAN programs in any language'', or the opposite that one cannot think in an object-oriented way and work in a non-object oriented language. Simply, that thinking in an object-oriented way and working in an object-oriented language go naturally together.

[audio] [real] Text to accompany slide09, in Chapter 1 of An Introduction to Object-Oriented Programming