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"[1] (http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html).
Well-known Turing tarpits include
- PDP-8 assembly language (one of the few commercially successful Turing tarpits)
- Brainfuck
- OISC (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 and Jot: 1 instruction, 2 symbols.