Turing Trap

Being TuringComplete and being "good" are not necessarily related.

The TuringTrap is based on the EquivocationFallacy (one of the FallaciousArguments). When discussing the relative merits of programming languages, any argument that language A is better than language B can be refuted by saying that, since both languages are TuringComplete, they are equivalent, and one cannot be better than the other.

The fallacy is in equivocation: you're shifting the meaning of quality from whatever original meaning was referenced in the argument (efficiency, elegance, readability, etc.) to Turing completeness.

As PaulGraham notes in OnLisp, "In principle, of course, any Turing-equivalent programming language can do the same things as any other. But that kind of power is not what programming languages are about. In principle, anything you can do with a programming language you can do with a Turing machine; in practice, programming a Turing machine is not worth the trouble."

One admittedly-limited but useful path out of the trap is the ChomskyHierarchy, which ranks languages based on the complexity of a virtual machine needed to implement the language (and thus, indirectly, its expressiveness, except in pathological cases).

Anyway, a lot of people will say, "Language X is more expressive than language Y," at which point, I think it's valid to bring in TuringEquivalence?. That's the only time I've ever really used it. What is expressiveness anyway?

Expressiveness doesn't imply an effect on TuringEquivalence?, except in the most rudimentary way. X is more expressive than Y means that for a given task, the resulting code conveys the solution more completely and with less noise using X than using Y. For example, take the following code for iterating over an array in C, Python, and SmallTalk:

 for (int i = 0; i < nElems; ++i){ 
     doSomething(elemArray[i]);
 }

 for elem in elemArray:
     doSomething(elem)

 elemArray Do:[:elem|doSomething: elem].

The Python version can be said to be more expressive than the C version, because it says exactly what it's doing without any extraneous verbiage like a loop counter. Note that this doesn't prove that C is [in general] less expressive than Python, just that it is for array iteration. [Note also that I do think that the general statement is true as well; it's just not proven by this one example.]

Well, that may be one way of interpreting 'expressiveness', but I've always interpreted it as 'I can express such and such logic in this language'. I usually heard it in regards to BASIC vs. some RealLanguage. E.g. you can do recursion or you can have more than 26 variables or whatever.

Which has nothing to do with Turing-completeness--the term "expressive" is being used for two different things by two different speakers above.

To be absolutely honest about Basic, you can fake things to a certain extent even given the most minimal of the commonly-used interpreters. Arrays can be used to fake having more than 26 variables, and recursion can be factored out with things like optimizing tail recursion into a re-initialization and a goto.

But that brings us back to the things mentioned in this article already, and in the TuringTarpit article: Basic simply lacks the primitives you need to program cleanly and with a minimum of noise. Therefore, Basic is commonly said to be lacking in expressiveness: You need to re-invent the wheel to do things that are done for you in most other languages. C is this way, too, sometimes, especially with MemoryManagement and its StandardIo? library (GetsIsDangerous, but there it is, sitting like a malign spirit). C is very expressive in doing low-level and speed-critical stuff in a reasonably portable way, plus it fits in the head neatly (an argument for a certain economy in language design). I'm sure Python is lacking in expressiveness in a few ways, too, but I'm not a Python guy.

Because you're not a Python guy, you don't have anything bad to say about Python? Would more evaluations were conducted in this manner. :)