Turing tarpit

Encyclopedia : T : TU : TUR : Turing tarpit

A Turing tarpit is a programming language designed to be Turing-complete while in some sense simplifying to the greatest extent possible both the syntax and the semantics of the language. Such a language gives up certain practical goals (such as ease of coding, performance, etc.) in favor of others (e.g., proving non-computability of certain functions, illustrating basic principles of programming, providing simple bases for computational models, etc.). Thus it is of interest in theoretical computer science.

Originally: "54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." --Alan Perlis, "Epigrams on Programming" [link].

Well-known Turing tarpits include

Brainfuck
Cellular automata
Combinatory logic, especially binary combinatory logic
INTERCAL
Pure untyped lambda calculus
OISC (a machine whose only instruction is "subtract and branch if negative")
PDP-8 assembly language (one of the few commercially successful Turing tarpits)
The Turing machine itself
Unlambda

There are two sometimes-divergent approaches with which computer scientists struggle when designing a tarpit: one may lean towards fewer instructions, or one may lean towards fewer recognized symbols. Some results of this struggle have been

Binary combinatory logic: 2 term-rewriting rules, 2 symbols
Brainfuck: 8 instructions, 8 symbols
Iota and Jot: 2 operations, 2 symbols
OISC: 1 instruction, 11+ symbols
Thue: 1 Instruction, 128+ symbols

The phrase the Turing tarpit is also heard occasionally in arguments between proponents of two or more different programming languages each claiming their language is better than the other(s). It refers to the tendency of participants in these discussions to attempt to encode the constructs or programming idioms of one language in another to justify claims of the form, "Anything you can do in your language, I can do in my language." When these encodings become so complex that they amount to writing an interpreter for the first language in the second, they cease to be informative (because in principle an interpreter for any Turing-complete language can be written in any other Turing-complete language) and the conversation is said to have entered the Turing tarpit.

The fact that the vast majority of general-purpose programming languages are equivalent in computational power is seen by some as implying that all arguments over which of two or more languages is best are pointless. Others maintain that it only means such arguments should be confined to properties of languages that actually do vary, such as their effects on programmer efficiency or their amenability to efficient implementations.

Turing tarpit

See also