Turing Tarpit

Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy. -- AlanPerlis

Refers to any language or system that is TuringComplete but minimalistic, supporting a bare minimum of operations or a very terse notation. Such a language may be interesting from a theoretical standpoint, but is impractical for use by human programmers. (Although some such languages are good candidates for IntermediateRepresentation? like ByteCode.)

The first such things were combinatorial logic, lambda calculus, and Turing machines, each of which can compute any computable function, and each of which is equivalent to the others by virtue of being able to simulate each of the others.

As a small example of the "tarpit" problem with such things, typically arithmetic is expressed in unary (base 1), which requires exponentially more space, time, and programming effort to deal with than do systems that use more conventional number bases such as base two.

Of course, since anything computable can be expressed in them, you can certainly set up a system for doing arithmetic in e.g. binary, but it is a nontrivial exercise to do so.

Similarly it can be possible but difficult and WriteOnly? to do certain things in certain programming languages. For instance, recursive algorithms in classic dialects of Basic might be simulated "by hand" using arrays to hold temporary values, but the result tends to be bug-ridden and highly opaque compared with the same algorithm expressed in a language with natural native support for functional recursion. Thus recursion is a TuringTarpit in classic Basic.

On the other hand, Basic always had reasonable string handling, whereas standard Pascal did not (it allowed only fixed length character arrays, for one thing), so Pascal was TuringTarpit in that particular area.

One (semi-) popular kind of TuringTarpit are the EsotericProgrammingLanguages, which are often designed as a kind of twisted exercise in humor.

Such languages demonstrate that, while many programming languages are TuringEquivalent, they are not equivalent for the purpose of expressing the intent of the programmer. Skilled programming language designers intentionally add SyntacticSugar and some extra verbosity to make their languages useful.

They also have their educational value; many of them show just how unusual or minimal a language can be while still remaining TuringComplete.

See http://www.wikipedia.com/wiki/Turing_tarpit

See also the Turing Tarpit, a catalogue of bad languages: http://www.geocities.com/ResearchTriangle/Station/2266/tarpit/tarpit.html

Examples: BefungeLanguage, BrainfuckLanguage, SnuspLanguage, InterCal, UnLambdaLanguage, MalbolgeLanguage, URISC (Sidenote: Malbolge is almost certainly not TuringComplete. InterCal is not minimalistic. BefungeLanguage is not a "bare minimum" approach either.) Also, it should be noted that the EsotericProgrammingLanguages? have not been peddled, FTMP, as SilverBullets. There are many other TuringTarpits OTOH, that have.

See also LambdaCalculus, EssAndKayCombinators, LittleLanguage, MinimalistLanguage, EsotericProgrammingLanguage, TuringTrap

Shouldn't UnLambdaLanguage and its ilk instead be called a ChurchQuagmire?? While the ChurchTuringThesis says the two types of PissPoorProgrammingLanguages? are in fact computationally equivalent, calling a FunctionalProgrammingLanguage a TuringAnything? is sure to annoy the FunctionalWeenies....

Another kind of TuringTarpit is implicit in the claim that "ThereIsNothingPerlCannotDo!"

Programmers often fall into the Turing tarpit when arguing about how powerful languages are. For example, a common exchange is for a SmugLispWeenie to go off on how Lisp is more powerful than other languages. Then some SmugFooWeenie? will point out that of course Lisp is not more powerful than Foo, you moron, since they are both TuringEquivalent. And then the SmugLispWeenie will explain for the gazillionth time that what he means by "more powerful" is that there are things you can do in Lisp that you can't do in Foo without ImplementingLisp (or some domain-independent thing of similar complexity) first. (See GreenspunsTenthRuleOfProgramming.)

Here is my example: http://www.oriontransfer.co.nz/research/register-machine-interpreter/index -- Samuel