Turing tarpit
From Wikipedia, the free encyclopedia
Turing tar pit is a general term for one of the various esoteric programming languages designed to be Turing-complete while in some sense simplifying to the greatest extent possible both the syntax and the semantics of the language. Such a language gives up certain practical goals (such as ease of coding, performance, etc.) in favor of others (e.g., proving non-computability of certain functions, illustrating basic principles of programming, providing simple bases for computational models, etc.). Thus it is of interest 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].
[edit] Examples
Well-known Turing tarpits include
- Brainfuck
- Combinatory logic, especially binary combinatory logic
- INTERCAL
- Pure untyped lambda calculus
- OISC (a machine whose instruction set contains only one instruction doing something like "subtract and branch if negative")
- PDP-8 assembly language (one of the few commercially successful Turing tarpits)
- The Turing machine itself
- Unlambda
There are two sometimes-divergent approaches with which computer scientists struggle when designing a tarpit: one may lean towards fewer instructions, or one may lean towards fewer recognized symbols. Some results of this struggle have been
- Binary combinatory logic: 2 term-rewriting rules, 2 symbols
- Brainfuck: 8 instructions, 8 symbols
- Iota and Jot: 2 operations, 2 symbols
- OISC: 1 instruction, 3 symbols (signed unary with a separator)
- Thue: 1 Instruction, 128+ symbols
[edit] References
- Alan Perlis, Epigrams on Programming, SIGPLAN Notices Vol. 17, No. 9, September 1982, pages 7 - 13.
