Turing tarpit
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
