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