Universelle Turingmaschine

Eine universelle Turingmaschine (UTM) ist in der Informatik eine Turingmaschine, die eine beliebige Turingmaschine auf beliebiger Eingabe simuliert. Die universelle Maschine erreicht dies im Wesentlichen dadurch, dass sie sowohl die Beschreibung der zu simulierenden Maschine als auch die Eingabe an diese Maschine von ihrem eigenen Band liest. Alan Turing stellte die Idee einer solchen Maschine in den Jahren 1936 bis 1937 vor. Dieses Prinzip gilt als Ursprung der Idee eines speicherprogrammierten Computers, den John von Neumann 1946 für das "Electronic Computing Instrument" verwendete, das heute von Neumanns Namen trägt: die Von-Neumann-Architektur.

In Bezug auf die Rechenkomplexität muss eine universelle Turingmaschine mit mehreren Bändern nur um einen logarithmischen Faktor langsamer sein als die Maschinen, die sie simuliert.