Universal machine
- This article is about the computer science concept, for the esoteric virtual machine, see UM-32.
Universal machines are programs which simulate other machines of their class. The most common universal machines are universal Turing machines (UTMs), which are Turing machine programs which simulate the behavior of a Turing-complete system.
Universal machines consist of the following:
- Machine; which is a language (e.g. Brainfuck, Python, lambda calculus), machine (Turing machine, Minsky machine), or other computational model.
- Program description; a fixed, bounded description consisting of some amount of symbols or states which the machine executes.
- Some input program description; which the fixed program evaluates. A universal machine can be re-run with arbitrary input programs while leaving the machine and fixed program descriptions the same.
Traditionally, a UTM will be given the input program description on its tape, with the machine starting up with its tape somehow pre-initialized with the given program. Universal machines which accept input "interactively" through some input instruction are also acceptable. Thus, a universal machine can be implemented in a language which lacks I/O, assuming there's some agreed upon way that the storage mechanisms could be initialized before the machine is operated.
Universal machines have implications for the computational class of the language they are implemented in. In most cases, if there is a Turing complete universal machine written in a given language, the language itself is Turing complete. This is not strictly true, however. It is possible to create a language where the only valid program is a universal machine. If this is the case, the machine or language is considered ℒ-complete. It's arguable whether or not such a system is Turing complete. On one hand, yes, the system can simulate a Turing complete system. On the other, it can only do so if the program for the simulated machine is given as a description to the machine, there is no way to translate a given machine into a program description for the underlying machine, only a way to translate one to a description for the simulated one.
Example universal machines
- UT19 a 19 tag program for 2-tag systems
- Grill Tag#Turing machine implementation a 2 state, 14 symbol machine in Grill Tag
External resources
- UTM for URM a 5 register machine for a modified form of Minsky machines