List of Turing-complete models of computation
Many people want to make new and unique Esolangs. Or base an Esolang on something a million others have done. That works too.
Unfortunately, there is no central resource to find out about interesting and esoteric models of computation. That's where this page comes in.
Models
Turing machines
(Included for completeness)
A Turing machine is a simple machine that works with a Reader Head, a Symbol Tape, and a Rule Table. The Reader head moves along the tape and, based on what the rule table says regarding its current state and the current cell's symbol:
- Changes the current cell's symbol
- Changes state
- Goes either left or right
If at any point the Turing Machine enters the special halt state, execution halts immediately.
It is the original [citation needed] Turing complete thing (hence the name).
An esoteric example is Brainfuck, sort of.
Turing Script is built on one of these, using Turing Machine programs as subroutines.
Lambda calculus
The original author was too stupid to understand Lambda calculus, and if you're reading this, no one has fixed this yet (OR you're looking at an old article).
Combinatory logic
Combinatory logic is similar to the lambda calculus, and thus the author doesn't understand those very well, either. See the Combinatory logic page for details.
Concatenative calculus
Concatenative calculus is similar to the combinatory logic, but function application is replaced by function composition as the default operation. It has similar properties to lambda calculus and combinatory logic, but makes it easier to incorporate non-pure aspects of the language, like I/O or variables.
The first concatenative language was Forth, but Factor is an example closer to the concatenative calculus ideas.
An esoteric example is Brainfuck Encoded Concatenative Calculus.
Unrestricted grammar
An Unrestricted grammar is basically what you'll find in Thue. (This section needs to be improved)