List of Turing-complete models of computation

From Esolang
Jump to: navigation, search

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.

Unrestricted grammar

An Unrestricted grammar is basically what you'll find in Thue. (This section needs to be improved)

See also

Category:Computational models