v4.0.6.3.0 (Master) Berechenbarkeit - T-Prädikat

Описание: Wenn wir eine universelle Turing-Machine haben, können wir sie mit jeweils nur einer kleinen Änderung umbauen zu
einem Programm, welches ein Execution Trace eines Programms schreibt
einen Debugger
einer Implementierung des Kleene'schen T-Prädikats
einer Implementierung der beschränkten Haltefunktion

Da unsere UTM nur an einer Stelle echt μ-rekursiv ist, können wir ablesen, dass T-Prädikat und Haltefunktion sogar primitiv-rekursiv sind.

Kleene sein T-Prädikat prüft, ob ein gegebenes Execution Trace File (eine Ausführung, ein Pfad im Konfigurationsraum) mit einer gegebenen Turing-Maschine und gegebenen Input hätte erzeugt werden können.

Präsentiert:
Von Jörg Kunze

Voraussetzungen:
Universelle Turing-Maschine, Berechenbare Funktionen, Gödel-Nummern, Turing-Maschinen-Nummer, μ-rekursiv, primitiv-rekursiv

Meine Videos:
Siehe auch in den folgenden Videos:

v4.0.6.3 (Master) Berechenbarkeit - Universelle Turing-Maschine
   • v4.0.6.3 (Master) Berechenbarkeit - Univer...  

v4.0.3.2 (Master) Berechenbarkeit - Turing-Maschine Berechnung
   • v4.0.3.2 (Master) Berechenbarkeit - Turing...  

v4.0.3 (Master) Berechenbarkeit - Turing Maschine
   • v4.0.3 (Master) Berechenbarkeit - Turing M...  

Quellen:
Siehe auch in den folgenden Seiten:

https://de.wikipedia.org/wiki/Univers...
https://en.wikipedia.org/wiki/Kleene%...
https://en.wikipedia.org/wiki/Tracing...)
https://en.wikipedia.org/wiki/Debugging

Buch:

Grundlage ist folgendes Buch:
Computability
A Mathematical Sketchbook
Douglas S. Bridges
Springer-Verlag New York Inc. 2013
978-1-4612-6925-0 (ISBN)

Sehr schön aber dichter:
Turing Computability: Theory and Applications
Robert I. Soare
Springer-Verlag New York Inc. 2016
978-3-6423-1932-7 (ISBN)

Lizenz:
Dieser Text und das Video sind freie Software. Sie können es unter den Bedingungen der
GNU General Public License, wie von der Free Software Foundation veröffentlicht, weitergeben
und/oder modifizieren, entweder gemäß Version 3 der Lizenz oder (nach Ihrer Option) jeder späteren Version.

Die Veröffentlichung von Text und Video erfolgt in der Hoffnung, dass es Ihnen von Nutzen sein wird,
aber OHNE IRGENDEINE GARANTIE, sogar ohne die implizite Garantie der MARKTREIFE oder der
VERWENDBARKEIT FÜR EINEN BESTIMMTEN ZWECK. Details finden Sie in der GNU General Public License.

Sie sollten ein Exemplar der GNU General Public License zusammen mit diesem Text erhalten haben
(zu finden im selben Git-Projekt).
Falls nicht, siehe http://www.gnu.org/licenses/