Turing tarpit

Turing tarpit

Turing tar pit 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, etc.). Thus it is of interest in theoretical computer science. (Many esoteric programming languages are also Turing tarpits.)

Originally: "54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." --Alan Perlis, "Epigrams on Programming" [http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html] .


Well-known Turing tarpits include
*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

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


# Alan Perlis, [http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html Epigrams on Programming] , SIGPLAN Notices Vol. 17, No. 9, September 1982, pages 7 - 13.

ee also

*Greenspun's Tenth Rule
*Zawinski's law of software envelopment

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Turing tarpit — noun The situation in which a programming language is only minimally Turing complete, so that everything is possible but nothing is easy . <!Perlis words The basic reason for increasing the size of the language is the so called Turing tarpit:… …   Wiktionary

  • Tarpit (networking) — A tarpit (also known as Teergrube, the German word for tarpit) is a service on a computer system (usually a server) that delays incoming connections for as long as possible. The technique was developed as a defense against a computer worm, and… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Turing completeness — For the usage of this term in the theory of relative computability by oracle machines, see Turing reduction. In computability theory, a system of data manipulation rules (such as an instruction set, a programming language, or a cellular… …   Wikipedia

  • Esoteric programming language — An esoteric programming language (sometimes shortened to esolang) is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke. There is usually no intention of the… …   Wikipedia

  • Tar pit (disambiguation) — A tar pit is a geological occurrence where subterranean bitumen leaks to the surface, creating a large puddle, pit, or lake of asphalt.Tarpit may also refer to:* Tar Pit (comics), a fictional supervillain in the DC Comics * Tarpit (networking),… …   Wikipedia

  • Algorithm examples — This article Algorithm examples supplements Algorithm and Algorithm characterizations. = An example: Algorithm specification of addition m+n =Choice of machine model:This problem has not been resolved by the mathematics community. There is no… …   Wikipedia

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

  • One instruction set computer — Computer science portal A one instruction set computer (OISC), sometimes called an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”