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

Retrieved from "http://www.centipedia.com/articles/Turing_tarpit"

This page has been accessed 544 times. This page was last modified 23:26, 13 Aug 2004. All text is available under the terms of the GNU Free Documentation License (see Copyrights for details).