Direkt zum Inhalt

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 Halteproblem semientscheidbar bzw. rekursiv aufzählbar ist.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos