Lexikon der Mathematik: universelle Turing-Maschine
eine Turing- Maschine, die in der Lage ist, die Rechnung jeder anderen Turing-Maschine zu simulieren.
Gestartet mit (der Codierung der) Zahlen n und x auf dem Eingabeband verhält sich die universelle Turing-Maschine genauso wie die n-te Turing-Maschine, angesetzt auf x. Die „n-te Turing-Maschine“ erhält man hierbei durch Arithmetisierung.
Insbesondere hält die universelle Turing-Maschine bei Eingabe von (n, x) genau dann, wenn die n-te Turing-Maschine bei Eingabe von x hält. Die Existenz der universellen Turing-Maschine zeigt daher, daß das allgemeine Halteproblemsemientscheidbar bzw. rekursiv aufzählbar ist.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.