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

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.