Turing tarpit - Definition and Overview

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
• 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 and Jot: 1 instruction, 2 symbols