Everything is at the bottom. Turing’s tar pit

The Turing Machine in all its glory.

What is the best programming language to choose? Of course, very often the choice of language depends on what this or that program is written for, and simply on the personal predilections of the programmer. The choice, as a rule, goes among more or less well-known languages, starting from various variations of C and can end anywhere. Although, of course, this or that thing in one language or another will be much more difficult to write than in another. But what about languages ​​where it’s hard to write basically anything because, for example, the syntax consists of eight commands? Such languages ​​are called “Esoteric Programming Languages”, or simply “Turing’s Tar Pit”. I propose to immediately see what the devils are found in this still pool.

For starters, what does Turing have to do with it? There is such an abstract computer as the “Turing Machine”, which is a visualization of the algorithm. It consists of an endless tape with cells and a record head that can move along the tape and change the values ​​of the cells according to some predefined rules. Sounds a lot like how programming works, doesn’t it? From this grow the legs of the “Turing completeness” criterion, i.e., the ability to implement any computable function on it with the help of one or another programming language (i.e., the algorithm for moving the head along the tape). Then what is a “tar pit”?

As mentioned above, “Turing tar pit” (a.k.a. “Turing quagmire”, “Turing tarpit”) is a programming language that has a very poor or very … non-standard syntax. Moreover, each of them is a fully functional and Turing-complete language. Why do they then exist at all, if it is difficult, inconvenient to use them, and in general there are a bunch of other languages? Well, the question is open. Some of them (like Brainfuck) are used for very specific purposes, but most of them were written for the sake of argument or “for fun”. At least one (Malbolge) was specifically written to mock programmers.

No, well, judge for yourself. First, Malbolge, being binary, performs all operations with ternary digits. Secondly, after each instruction is executed, it is encrypted two times. Thirdly, out of eight commands, one does nothing, one terminates the program, one is needed to move to another cell, and all the rest are used to perform all sorts of devilry in the spirit of “Shift register d by one ternary digit to the right and store in registers d and a”. Just to give an example, the first Malbolge program appeared two years after the language was written. At the moment, there are only five programs on Malbolge – two versions of “Hello, world!”, A program that displays its own code on the screen (was generated by another computer in 14 years), “Cat” (a program that immediately displays whatever the user types) , as well as the text of the song-cycle “99 bottles of beer”. The language, for a second, was written in 1998.

If anything, “Hello World” looks like this:




The complete opposite of him is Brainfuck. This is the easiest language to learn, with the most simple commands, which, by the way, are also only 8. This is literally a Turing virtual machine – the Brainfuck syntax consists of commands to shift the write head left-right, decrease-increase the current value by one, read-write and organizing a while-loop. At the same time, again, Turing-complete (Write a Brainfuck emulator in some language – automatically prove its completeness). It is mainly used to explain the very basics of programming (by those who know about it), writing compilers, interpreters, and studying optimizations. Well, in a good way, it was with the story about Brainfuck that the article should have begun – after all, it was he who created computer esotericism in 1993, something like gymnastics in the field of scientific creativity – “how to dodge so that everyone around was stunned.”


hello world on brainfuck

The apotheosis of all this will be Whitespace, also known as “Brainfuck for spies”. A feature of this language is that its entire syntax consists of spaces, tabs and line breaks. The code on Whitespace literally looks like a blank slate. At the same time, the set of commands is quite wide – as many as 24 pieces. Purely theoretically, if it is not some Python or Forth, a Whitespace program can be hidden inside another program and enjoy the spectacle. It is also worth noting that most of the programs in this language were obtained using assembler, and not written by hand (although there are some).


Hello World on Whitespace. Blue is tab, red is space

It would seem that what could be more delusional than a language whose code is a chilling void? Here it is, the bottom of the tar pit has been reached.
And then there was a knock from below. Ladies and gentlemen, meet Shakespeare! A language that – I’m not kidding now – imitates the plays of Shakespeare. Variables in it are set in the characters section, they must be assigned names. Commands like “Open your heart” or “Speak your mind” are used for output. But most of all I like the way operations with numbers are arranged. In Shakespeare, each noun has a value of either 1 or 0 (depending on whether the object/concept is beautiful or not. For example, “Flowers” has a value of 1, and an ugly “Pig” has a value of 0. Neutral nouns have a value of 1). Each adjective doubles the meaning (and the next doubles the new meaning). Values ​​are assigned by referring to a variable character (i.e., literally “you”), accompanied, for example, by a stream of insults. Arithmetic operations, fortunately, work fine (“You are the difference between a square of a filthy creature and a donkey” etc.). Since only two characters can be on the stage, periodically one of them must be removed with the command [Exit персонаж] and enter another command [Enter персонаж]. All characters are driven by the team [Exeunt]. Simplifying – we still have the same Brainfuck with its minimal syntax, only much more confusing.

Of course, there are many more languages ​​written “for fun”, as I said before. For example, the many imitators of Brainfuck, such as the multi-tasking Brainfork, F*ckF*ck (each instruction is an uncensored word with an asterisk), or DoubleFuck. In the genre of pure farce, the language Whenever arises, the instructions of which are executed in a random order, and not in the one in which they are written. Similar ideas are embedded in the poignantly satirical Java2k—just as Sun’s original Java “deallocates memory at random intervals,” Java2k programs have multiple alternatives to each function, and which alternative to execute is decided randomly at runtime. In the same paradigm of “random” or “side” programming, Fish Programming Language is built (Programming Language of the Fish) all work takes place on the image of a fish, divided into many parts that randomly change their color.

And in general, do not dive into the Turing tar pit – everything can be done there, but none of this will come easy to you.

PS As it turned out, Turing Tarpit is also a musical group. Here is their album cover (as well as developer status on Brainfuck)


Similar Posts

Leave a Reply