- Turing tarpit
Turing tar pit is a general term for a
programming languagedesigned to be Turing-completewhile 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. (Many esoteric programming languages are also Turing tarpits.)
Originally: "54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." --
Alan Perlis, " Epigrams on Programming" [http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html] .
Well-known Turing tarpits include
Combinatory logic, especially binary combinatory logic
OISC(a machine whose instruction set contains only one instruction doing something like "subtract and branch if negative")
PDP-8assembly language (one of the few commercially successful Turing tarpits)
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, 3 symbols (signed unary with a separator)
*Thue: 1 Instruction, 128+ symbols
# Alan Perlis, [http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html Epigrams on Programming] , SIGPLAN Notices Vol. 17, No. 9, September 1982, pages 7 - 13.
Greenspun's Tenth Rule
Zawinski's law of software envelopment
Wikimedia Foundation. 2010.