Diskussion:Smn-Theorem

wersagt das das berechenbar ist??!! (nicht signierter Beitrag von 217.231.102.79 (Diskussion | Beiträge) 10:43, 23. Mär. 2010 (CET))

Um nach all der Zeit doch noch mal eine Antwort zu geben:

Das sagte zuerst Stephen Cole Kleene in seinen frühen Arbeiten über berechenbare Funktionen und rekursive Notationssysteme für Ordinalzahlen. Wie das in der Mathematik üblich ist, hat er seine Aussagen sogar bewiesen. Allerdings sind diese Beweise sehr kompliziert, da er Berechenbarkeit noch in der Sprache der Arithmetik ausdrücken musste. Ein (etwas) schlankerer Beweis findet sich bei Rogers. Im heutigen Computerzeitalter ist ein Beweis allerdings deutlich praktischer möglich:

Man nehme sich eine Programmiersprache seines Vertrauens und schreibe sich ein Programm, dass zwei Eingaben erwartet (nennen wir sie $p$ und $c$) und zunächst $c$ dort in den Arbeitsspeicher schreibt, wo das Betriebssystem selbst Eingaben ablegen würde und danach das Programm $p$ ggf. auf weiteren Eingaben ausführt. Gemeint ist dabei $p$ als diejenige Zahl, die im Arbeitsspeicher steht wenn man all die Speicherzellen mit dem Programmcode hintereinander gelesen als Binärzahl auffassen würde.

Das man (mit einiger Übung und den entsprechenden Zugriffsrechten) ein solches Programm schreiben, kompilieren und ausführen kann, ist dann schon der Beweis. Die interne Repräsentation im Speicher ist dann nämlich gerade die gewünschte Gödel-Nummer $s(p;c)$ für die gilt $\psi _{s(p;c)}(x)=\psi _{p}(c;x)$. Das ist berechenbar... nun weil's ja berechnet wird, von meinem Computer. Der Rest sind ein paar formale Kleinigkeiten, wie die Feststellung, dass die gewählte Programmiersprache Turing-vollständig ist ($\psi \approx \varphi$) und, dass man statt eines einzelnen $c$ auch einfach beliebig viele Parameter hätte nehmen können.

Liebe Grüße --84.19.199.240 00:51, 15. Mär. 2015 (CET)