Minsky machine
A Minsky machine is a finite-state automaton with access to a number of unbounded registers or counters. These registers can be thought of as monosymbolic stacks (i.e. stacks of all the same symbol.) Two operations are available on each register:
- increment it; and
- decrement it unless it is zero, in which case follow an alternate state transition.
Minsky machines with two or more registers have been shown to be in the same computational class as Turing machines. Because of this, and because of their simplicity, they can be used to prove several esoteric programming languages to be Turing-complete as well.
The canonical reference is Minsky's book, Computation: Finite and Infinite Machines (Prentice-Hall International, 1967; ISBN 0131655639), in which he calls these machines program machines. He also describes a variation which is Turing-complete with only one register; this variation requires that the machine has operations to:
- multiply the register by a constant; and
- check to see if it is divisible by a constant, and if so, divide by that constant and effect an alternate state transition.
A proof of Turing-completeness is also given in the textbook Aho, Ullman, The Theory of Parsing, Translation, and Compiling, (1972; ISBN 0139145567).
See also
- OISC
- Portable Minsky Machine Notation
- Szewczyk notation for Minsky machine
- Generalized Minsky machine, a generalization allowing an arbitrary universe of recursive polynomial types instead of just .
- Alternating 1-based Minsky machine
- Mel
