Universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of machine to be simulated as well as the input thereof from its own tape.  This model is considered by some to be the origin of the stored program computer—used by John von Neumann for the “Electronic Computing Instrument” that now bears von Neumann’s name: the von Neumann architecture.

Universal machine is also known as universal computing machine, universal machine, machine U, U.

UTM

Alan Turing described his construction in complete detail in his 1936 paper:

“It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D [“standard description” of an action table] of some computing machine M, then U will compute the same sequence as M.

Universal Turing Machine uses numbers in its tape as input and as output. Its commands are Left, Right and  Skip.

Symbolic Abstract Machine (SAM) compared with UTM

SAM differs from UTM, because it can use higher abstraction symbols as its input and output. The logic for each symbol is written into the symbol: the command-fact. By applying these two modifications it is possible to create a higher abstraction UTM, which is capable of simulating typical programming languages.

SymbolicAbstractMachine

We can  describe our novel construction in complete detail:

“It is possible to invent a single machine which can be used to compute any computable sequence using programming language semantics. If this machine SAM is supplied with a tape on the beginning of which is written the S.D [“standard description” of an action table] of some computing machine M, then SAM will compute the same sequence as M.”
If we thing each symbol to work like an atomic formula, only containing one reductionist formula, the construction of a symbol resembles the one of the metaphor of an atom. Hence, our SAM works using atoms, each atom containing an automaton, in the way that UTM has.

Some links:

Advertisements