Arbitrary effect at an arbitrary point

From Esolang
Jump to: navigation, search

Being able to achieve an arbitrary effect at an arbitrary point is one of the subtler requirements for a programming language to be Turing-complete. The phrase can be seen as a generalized statement of the idea that a Turing machine's control mechanism must be allowed to be an unrestricted finite-state automaton. That is, placing any restriction on the FSA that cannot be "worked around" will render it unable to perform some computations that could otherwise be performed by a standard Turing machine.

As a pathological example of a programming language which has loops, conditionals, an unbounded store, but which is not Turing-complete because it does not allow an arbitrary effect at an arbitrary point, take a version of Brainfuck in which each > instruction must be followed immediately by a < instruction.

Most programming languages do allow for arbitrary effects at arbitrary points. In the imperative paradigm, for example, all this really means is that there is no restriction on the order that instructions are specified to be executed in.

Some esoteric programming languages, though, do not allow one to directly code arbitrary effects at arbitrary points. These effects must be achieved circuitously. This makes them simultaneously very interesting to program in and very difficult to prove Turing-complete, because one must show that it is possible to achieve each needed effect indirectly and compositely; that is, through a combination of directly specified effects. Notable examples include:

  • Malbolge - the operation to execute is given by the progression: C ← (C + [C]) mod 94
  • 2L - being able to execute a given operation relies on the current direction of travel
  • Aura - each operation writes a new next instruction
  • Beturing - control mechanism's flow graph must be planar