Main Page | See live article | Alphabetical index A Turing tarpit is a programming language designed to be Turing-complete while minimizing the number of distinct instructions. Such a language gives up practicality (such as ease of coding, performance, etc.) but is often useful 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". Well-known Turing tarpits include PDP-8 assembly language (one of the only commercially successful Turing tarpits) Brainfuck SBN (a machine whose only instruction is "subtract and branch if negative") Pure untyped lambda calculus Unlambda Combinatory logic Cellular automata The Turing machine itself There are two sometimes divergent ways of viewing the challenge of designing a tarpit, those which lean towards fewer instructions, and those which lean towards fewer symbols recognised. Some results of this struggle have been: Thue: 1 Instruction, 128+ symbols Brainfuck: 8 instructions, 8 symbols OISC: 1 instruction, 11+ symbols Iota/jot: 1 instruction, 2 symbols This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.