05 September 2011

Turing Completeness is not Practical Completeness

As a discussion comparing the relative merits of different programming languages grows longer, the probability of an appeal to Turing completeness as a measure of linguistic equivalence approaches 1. It's practically Godwin's law of programming languages.

Appealing as it is, the notion that whatever is possible in one language is possible in all is simply untrue. Turing completeness refers merely to the ability to implement any computable function. There are plenty of esoteric languages that have no or very limited I/O, and plenty of non-esoteric languages that have little to no ability to interface with libraries and other languages.

The fact that languages do differ in their strengths and weaknesses is precisely the main reason we use different languages at all. Different tools are best suited to different situations. The next time someone commits this fallacy, point them to the concept of the Turing tarpit, and if further investigation doesn't prove to them that theoretical equivalence is not the same as practical equivalence, invite them to implement a simple algorithm such as CRC32 in Brainfuck.

1 comment:

  1. Great website. I look forward to reading what 're planning on next, because your post is a nice read.