Brainfuck – How It Achieves Turing Completeness

A Turing tarpit is a kind of esoteric programming language which strives to be Turing-complete while using as few elements as possible. Brainfuck is perhaps the best-known tarpit, but there are many.

• Iota and Jot are functional languages with two and three symbols, respectively, based on the SK(I) combinator calculus.

• OISC (One Instruction Set Computer) denotes a type of imperative computation that requires only one instruction of one or more arguments, usually “subtract and branch if less than or equal to zero”, or “reverse subtract and skip if borrow”. The x86 MMU implements the former instruction and is thus Turing-complete.

In general, for an imperative language to be Turing-complete, it needs:

1. A form of conditional repetition or conditional jump (e.g., while, if+goto)

2. A way to read and write some form of storage (e.g., variables, tape)

For a lambda-calculus–based functional language to be TC, it needs:

1. The ability to abstract functions over arguments (e.g., lambda abstraction, quotation)

2. The ability to apply functions to arguments (e.g., reduction)

There are of course other ways of looking at computation, but these are common models for Turing tarpits. Note that real computers are not universal Turing machines because they do not have unbounded storage. Strictly speaking, they are “bounded storage machines”. If you were to keep adding memory to them, they would asymptotically approach Turing machines in power. However, even bounded storage machines and finite state machines are useful for computation; they are simply not universal.

Strictly speaking, I/O is not required for Turing-completeness; TC only asserts that a language can compute the function you want, not that it can show you the result. In practice, every useful language has a way of interacting with the world somehow.

Yes, if you admit a few instructions for transposition—uncommon but not unknown.

You can then interpret a piece as Choon, which is Turing-complete. The performer is the memory: they must remember the number of notes by which the piece is currently transposed, and all of the notes they have played thus far. Obviously it’s feasible only for a computer, or perhaps a savant.

From the Choon manual:

• Transpositions

  There are three transposition instructions, up (+), down (-) and cancel (.). A transposition instruction transposes all subsequent notes played by the amount of the last note played. The cancel instruction (.) sets the transposition back to zero.

  Transpositions are cumulative, so the Choon code to transpose future notes up by 2 is b+, and by 4 would be b++. Also, the value used is the value of the previous note after transpositions have been applied, so b+b+ transposes future notes up by 6, not by 4.

• John Cage

  The John Cage instruction (%) causes a one note silence in the output stream. The transposition value of a John Cage is zero - %- and %+ are no-ops (except that a single silence is added to the output).

• Repeat Bars

  The Repeat Bars instructions (||: and :||) enclose a loop. The loop will execute the number of times indicated by the most recent note played before the ||: was encountered. A zero or negative value will mean Choon will immediately jump to start playing from the matching :||. A John Cage means repeat forever - %||::|| is an infinite loop.

• Tuning Fork

  The Tuning Fork instruction ~ provides a way to break out of loops. If a tuning fork is encountered in a loop, and the last note played was a note of value A, then Choon will immediately jump to start playing from after the next :|| instruction. If there is no further :|| instruction (meaning ~ has been used outside any repeat bars), then the performance will immediately terminate.

• Markers

  Markers provide marvellous programming convenience. A marker is a lower case letter or word that remembers a point in the output stream. Referring to a marker (see below) will cause the note played after the Marker occurred to be played again. Note that transpositions will affect this newly played note.

  Where two or more markers occur sequentially, or a marker follows a play-from-marker instruction, they must be seperated by whitespace.

• Play From Output

  The Play From Output instruction (=) allows you to play again notes that have already been played in the output stream. You can refer to the notes by number - the 5th note played since the program began would be =5, by relative number - the 3rd most recent note played would be =-3 or by marker - the note played after marker x would be =x.

  It is a common idiom to re-use a marker and immediately then refer to it, like this: x=x. This is akin to saying x=x+y in a conventional programming language (where y represents the currently effective transposition value).

A John Cage is just a rest, a Tuning Fork is (roughly) dal segno, and a marker is a segno. I suppose the tuning fork could be played by an additional performer to whom the primary performer responds, but the principle is the same.