Universal Turing machine

related topics
{math, number, function}
{system, computer, user}
{theory, work, human}
{work, book, publish}
{style, bgcolor, rowspan}
{son, year, death}
{service, military, aircraft}

In computer science, a universal Turing machine 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. Alan Turing introduced this machine in 1936–1937. This model is considered by some (for example, Martin Davis (2000)) to be the origin of the stored program computer—used by John von Neumann (1946) for the "Electronic Computing Instrument" that now bears von Neumann's name: the von Neumann architecture. It is also known as universal computing machine, universal machine, machine U, U.

In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates.

Contents

Introduction

Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, we can encode the action table of any Turing machine in a string. Thus we can construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and computes the tape that the encoded Turing machine would have computed. Turing described such a construction in complete detail in his 1936 paper:


Stored-program computer

Davis makes a persuasive argument that Turing's conception of what is now known as "the stored-program computer", of placing the "action table" -- the instructions for the machine—in the same "memory" as the input data, strongly influenced John von Neumann's conception of the first discrete-symbol (as opposed to analog) computer—the EDVAC. Davis quotes Time magazine to this effect, that "everyone who taps at a keyboard... is working on an incarnation of a Turing machine," and that "John von Neumann [built] on the work of Alan Turing" (Davis 2000:193 quoting Time magazine of 29 March 1999).

Davis makes a case that Turing's Automatic Computing Engine (ACE) computer "anticipated" the notions of microprogramming (microcode) and RISC processors (Davis 2000:188). Knuth cites Turing's work on the ACE computer as designing "hardware to facilitate subroutine linkeage" (Knuth 1973:225); Davis also references this work as Turing's use of a hardware "stack" (Davis 2000:237 footnote 18).

As the Turing Machine was encouraging the construction of computers, the UTM was encouraging the development of the fledgling computer sciences. An early, if not the very first, assembler was proposed "by a young hot-shot programmer" for the EDVAC (Davis 2000:192). Von Neumann's "first serious program ... [was] to simply sort data efficiently" (Davis 2000:184). Knuth observes that the subroutine return embedded in the program itself rather than in special registers is attributable to von Neumann and Goldstine[2]. Knuth furthermore states that

Full article ▸

related documents
ANSI escape code
PL/I
Basic Encoding Rules
Netlist
HyperTalk
P-code machine
Bash
InterWiki
Turing completeness
Simula
Wikipedia:Free On-line Dictionary of Computing/O - Q
Lotus Improv
Unified Modeling Language
Universal Product Code
Ada (programming language)
Genetic programming
Dhrystone
Passphrase
Key (cryptography)
Defensive programming
One instruction set computer
Modula-2
S-expression
Compiler optimization
Queueing theory
Enterprise Objects Framework
PILOT
Pike (programming language)
COMMAND.COM
Maple (software)