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
East Marion, New York

... for a household in the town is $44,583, and the median income for a family is $52,500. Males have a median income of $47,917 versus $31,250 for females. The per capita ...

 
 
 
This page was created in 23.9 ms