Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Widerspruchsbeweis des Halteproblems
Autor
Universität/Hochschule Widerspruchsbeweis des Halteproblems
info_study
Neu Letzter Besuch: im letzten Monat
Dabei seit: 28.05.2022
Mitteilungen: 4
  Themenstart: 2022-05-28

Hallo. Ich habe mir den Widerspruchsbeweis für das Halteproblem auf dieser Seite angesehen: https://pierre.run/2015/10/das-halteproblem/ Anschließend habe ich den Sachverhalt als Python-Programm verdeutlicht: \sourceon nameDerSprache stop = True def M(P, E): return stop def Mstrich(U): if M(U, U): Mstrich(U) return True print(Mstrich(Mstrich)) \sourceoff Für die Funktion M muss man das Resultat stop manuell angeben, da wir innerhalb des Widerspruchsbeweises ja nur annehmen können, dass es eine total-berechenbare (entscheidbare) Funktion für das Halteproblem gibt und in Wirklichkeit gibt es die nunmal nicht. Was ich nicht verstehe ist, dass man ja prinzipiell anstelle von M auch jede beliebig andere Funktion nehmen könnte. Ich könnte auch eine Funktion M angeben, die True ausgibt, sobald das Ergebnis einer Addition richtig ist und Mstrich würde halt dann auch den Widerspruch ausgeben, wenn die Addition richtig ist. Deswegen verstehe ich den Beweis leider nicht und macht für mich auch kaum Sinn. Kann mir da einer weiterhelfen? Danke


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3788
  Beitrag No.1, eingetragen 2022-05-28

Wenn du für $M$ irgendeine Funktion einsetzt, kannst du natürlich auch dazu eine Funktion $M'$ konstruieren, die endlos läuft, wenn $M$ den Wert True zurückgibt, und anderenfalls anhält. Nur hast du damit keinerlei Widerspruch konstruiert. Das ist aber auch nicht zu erwarten, denn der Beweis will ja nicht zeigen, dass es überhaupt keine Funktionen $M$ gibt, sondern, dass es keine Funktion $M$ gibt, die das Halteproblem löst. Erst die Annahme, dass $M$ das Halteproblem löst, führt zum Widerspruch. --zippy


   Profil
info_study
Neu Letzter Besuch: im letzten Monat
Dabei seit: 28.05.2022
Mitteilungen: 4
  Beitrag No.2, vom Themenstarter, eingetragen 2022-05-29

Danke erstmal. Nur leider habe ich es immernoch nicht ganz verstanden. Warum führt erst die Annahme, dass M das Halteproblem löst, zum Widerspruch? Wenn ich für M das partiell-berechenbare Halteproblem angebe, wovon wir wissen, dass es das gibt: \sourceon nameDerSprache def M(P, e): P(e) return True def Mstrich(U): if M(U, U): Mstrich(U) return True print(Mstrich(Mstrich)) \sourceoff Dann gelange ich auch bei True in die Endlosschleife. Was ich mir hier bestenfalls noch vorstellen kann ist, dass man jetzt mit dem partiell-berechenbaren HP für Mstrich mit Parameter Mstrich zwar in die Endlosschleife kommt, aber nie auf True kommen kann. Die Endlosschleife wäre ja jetzt kein Widerspruch (weil sie ja nicht False ausgibt, wenn es hält), aber das True wäre ein Widerspruch, welches mit der total-berechenbaren Funktion ja erscheinen kann und mit der jetzigen Funktion nicht.


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3788
  Beitrag No.3, eingetragen 2022-05-29

\quoteon(2022-05-29 08:27 - info_study in Beitrag No. 2) Was ich mir hier bestenfalls noch vorstellen kann ist, dass man jetzt mit dem partiell-berechenbaren HP für Mstrich mit Parameter Mstrich zwar in die Endlosschleife kommt, aber nie auf True kommen kann. \quoteoff Ja, genauso ist es, denn aufgrund deiner Konstruktion ist doch klar, dass $M'(M')$ nie anhält. (Das ist einfach eine über zwei Funktionen verteilte Endlosschleife.)


   Profil
info_study
Neu Letzter Besuch: im letzten Monat
Dabei seit: 28.05.2022
Mitteilungen: 4
  Beitrag No.4, vom Themenstarter, eingetragen 2022-05-29

Vielen Dank. :-) Dann bin ich froh, dass ich mit meinen Gedankengängen richtig liege und das Thema verstanden habe.


   Profil
info_study
Neu Letzter Besuch: im letzten Monat
Dabei seit: 28.05.2022
Mitteilungen: 4
  Beitrag No.5, vom Themenstarter, eingetragen 2022-05-29

"Die Endlosschleife wäre ja jetzt kein Widerspruch (weil sie ja nicht False ausgibt, wenn es hält), aber das True wäre ein Widerspruch, welches mit der total-berechenbaren Funktion ja erscheinen kann und mit der jetzigen Funktion nicht." Ich habe mich auf der Seite (pierre.run/2015/10/das-halteproblem/) leider verlesen. Auch die Endlosschleife gilt als Widerspruch und somit stimmt ja mein Gedankengang doch nicht so ganz. :-( Und jetzt komme ich leider wieder an die Stelle, dass man für M ja auch die partiell-berechenbare Funktion für das Halteproblem angeben könnte und auch dort einen Widerspruch erhalten könnte, obwohl das partiell-berechenbare HP ja existiert. \sourceon nameDerSprache def M(P, e): P(e) return True def Mstrich(U): if M(U, U): Mstrich(U) return True def A(E): return 1 print(Mstrich(A)) \sourceoff Vielleicht ist meine Idee vom letzten Beitrag aber trotzdem nicht so falsch


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 3788
  Beitrag No.6, eingetragen 2022-05-29

\quoteon(2022-05-29 18:13 - info_study in Beitrag No. 5) Auch die Endlosschleife gilt als Widerspruch \quoteoff Was meinst du mit "gilt als Widerspruch"? Das hängt doch davon ab, was für eine Annahme du über $M$ machst: 1. Die Annahme, dass $M$ das Halteproblem löst, führt zu einem Widerspruch, weil $M(M',M')$ überhaupt kein Ergebnis liefert. 2. Die Annahme, dass $M$ eine partielle Lösung des Halteproblems realisiert, führt dagegen nicht zum Widerspruch, da $M(M',M')$ nicht True liefert.


   Profil
info_study hat die Antworten auf ihre/seine Frage gesehen.
info_study wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]