Turing tarpit
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources (ideally, using inline citations). Unsourced material may be challenged and removed. (June 2008) |
Turing tarpit is a general term for a programming language 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, general amusement, etc.). Thus it is of interest in theoretical computer science. Many esoteric programming languages are also Turing tarpits.
The term is also applied, on occasion, to the entire field of computer programming. That is, there are many programming problems which are interesting and possible to solve, in theory. However, few of them are easy.
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
- 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.
