Encyclopedia > Turing tarpit

  Article Content

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

Well-known Turing tarpits include

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/jot: 1 instruction, 2 symbols



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Photosynthesis

... to note that this chemical equation is highly simplified; in reality photosynthesis employs a very complex mechanism for the adsorbption and conversion of light into ...

 
 
 
This page was created in 29.7 ms