WikiDer > Universelle Turing-Maschine

In dem Mathematik und der Theoretische Informatik, ist ein universelle Turingmaschine (UTM) (auch bekannt als der Universalrechner, Universalmaschine (UM), du maschine,SIE und ein_TM) ein Turing Maschine dass irgendein Zufall Turing Maschine auf irgendeine zufällige Eingang können simulieren. Dies gelingt der universellen Turingmaschine im Wesentlichen dadurch, dass sie sowohl die Beschreibung der zu simulierenden Maschine als auch deren Input vom eigenen Band liest.

EIN universelle Turingmaschine ist ein Turing Maschine Das ${displaystyle langle M,wangle }$ nimmt als Eingabe und akzeptiert diese Eingabe, wenn:

• ${Anzeigestil M}$ ein richtiger Zeichenfolgencodierung stammt von einer Turingmaschine,
• ${Anzeigestil w}$ ein wort ist im alphabet der by ${Anzeigestil M}$ kodierte Turingmaschine und
• ${Anzeigestil M}$ für das Wort ${Anzeigestil w}$ stoppt im akzeptierenden Zustand

Nur wenn ${displaystyle langle M,wangle }$ Wenn alle diese Bedingungen erfüllt sind, stoppt die universelle Turingmaschine im akzeptierenden Zustand^[1]. Eine formale Notation ist: ${displaystyle A_{TM}={langle M,wangle mid M{ ext{ ist eine Turingmaschine und }}M{ ext{ akzeptiert }}w}}$.

Eine wichtige Beobachtung ist, dass die universelle Turingmaschine a Erkenner ist von ${displaystyle langle M,wangle }$, und deshalb nein Entscheidungsträger. Dies ist der Fall, weil M am Eingang . unendlich rechnen kann ${Anzeigestil w}$ und erreicht somit nie den ablehnenden Zustand. Die universelle Turingmaschine würde daher niemals in den negativen Zustand zurückkehren. Wir haben es hier damit zu tun Stoppproblem.

Die Idee einer universellen Turingmaschine wurde 1936 geboren^[2] Vorgestellt von Alan Turing. Dieses Modell wird von einigen (z. B. Martin Davis (2000)) als Ursprung des gespeichertes Programm Computer - durch John von Neumann (1946) für sein "Electronic Computing Instrument" verwendet, das heute seinen Namen trägt: de von Neumann-Architektur.

Der Alltagscomputer

Der Alltagscomputer wird manchmal als universelle Turingmaschine bezeichnet. Dies ist einerseits richtig, da das Prinzip der universellen Turingmaschine darin besteht, dass sie beliebige Programme mit beliebigen Eingaben ausführen kann; was auch praktisch machbar ist. Andererseits hat die theoretische universelle Turingmaschine ein unendliches Gedächtnis. Praktisch kann man sagen, dass ein Alltagscomputer eine universelle Turing-Maschine ist, da der Speicher, den die meisten Computer haben, für viele Probleme ausreicht, während dies rein theoretisch nicht richtig ist.

Verweise

• Martin Davis, Engines of Logic: Mathematiker und der Ursprung des Computers, 1. Auflage, 2000, New York NY, W.W. Norton & Company, ISBN 0-393-32229-7
• Alan Turing, Über berechenbare Zahlen, mit einer Anwendung auf das Entscheidungsproblem (siehe hier), Proceedings of the London Mathematical Society, 1936, vol. 42, Ausgabe 2
• Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem: A correct, Proceedings of the London Mathematical Society, 1937, vol. 43, Heft 6, S. 544-46, Nachdruck in Martin Davis Hrsg. (1965) Das Unentscheidbare, Raven Press, Hewlett NY S. 115–154; mit Korrekturen an Turings UTM von Emil Post siehe Fußnote 11 in Davis 1965, S. 299.