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
Anna Karenina

... the novel opens, Stiva's friend Levin has returned Moscow from his country estate with the intention of proposing to Kitty. He first meets Stiva who encourages ...

 
 
 
This page was created in 37.4 ms