Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Berechenbarkeit von Anzahl haltender Rechnungen
Autor
Universität/Hochschule Berechenbarkeit von Anzahl haltender Rechnungen
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Themenstart: 2021-07-17

Hi, ich schreibe am Montag eine Klausur und da wir keinerlei Feedback mehr zu Altklausuraufgaben bekommen können, versuche ich nun mal hier mein Glück. Wäre super, wenn mir jemand dabei helfen kann. https://matheplanet.com/matheplanet/nuke/html/uploads/b/53673_berech.png Ich komme hierbei nicht wirklich auf eine zufriedenstellende Lösung und komme nicht zu einem Entschluss. Meine Idee: Ich definiere eine Hilfsfunktion. h(M(w)) := 1, falls M(w) hält undef sonst h ist aufgrund der Semi-Entscheidbarkeit des Halteproblems auf jeden Fall berechenbar. Sei W = {w1,...,wn} die Menge der zu prüfenden Wörter. W ist endlich, da es nur eine begrenzte Anzahl an Wörtern der Länge k über einem gegebenen Alphabet gibt. Möglicher Algorithmus für fk: x = 0; for i = {1,...,n} x = x + h (M(wi)); return x; fk kann nur ein konkretes Ergebnis liefern, wenn M(w) für alle w hält. Dann gilt x = |W|. fk soll aber nicht berechnen, ob M für alle w hält, sondern eine konkrete Anzahl liefern. Dies ist aber nicht mehr möglich, sobald h einmal in den undef Fall kommt, somit ist fk nicht berechenbar. Freue mich über jegliche Anregung hierzu. Am schönsten wäre es natürlich, wenn mir jemand sagen kann, ob meine Überlegung hier Sinn macht, oder ob man doch für die Berechenbarkeit argumentieren kann. Viele Grüße


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.1, vom Themenstarter, eingetragen 2021-07-17

Hier als Nachtrag nochmal meine Idee für die andere Richtung, also dass fk berechenbar ist. Ich nutze den im Eingangspost aufgeführten Algorithmus. Komme ich mit h einmal in den Fall undef, ist fk undef. Also fk:= { |W| ,falls M(w) für alle w hält undef sonst


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2028
  Beitrag No.2, eingetragen 2021-07-18

Hallo Schutze, Deine Intuition bzw. Heuristik dafür, dass $f_k$ nicht berechenbar sein kann, stimmt zwar, ist aber letztlich keine ausreichende Begründung. Denn Du hast ja nur begründet, dass der von Dir angegebene naheliegende Algorithmus nicht funktionieren kann. Es könnte aber prinzipiell sein, dass es einen anderen Algorithmus gibt, der durchaus funktioniert ... Um die Nichtberechenbarkeit zu begründen, solltest Du vielmehr versuchen, eine als nicht berechenbar bekannte Funktion auf $f_k$ zu reduzieren. Es sollte Dir da natürlich direkt das Halteproblem in den Sinn kommen. Also: Wenn Du wissen willst, ob eine Maschine $M$ auf einer Eingabe $w \in \Sigma^\ast$ hält (das ist ja gerade die Frage des Halteproblems), wie könntest Du das mit Hilfe von $f_k$ entscheiden? (Tipp: Konstruiere dafür eine geeignete Turingmaschine $M'$ als Eingabe für $f_k$.) Viele Grüße und viel Erfolg Thorsten


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.3, vom Themenstarter, eingetragen 2021-07-18

Hallo Thorsten, Vielen Dank erstmal für deine Antwort. Das es hier darauf hinausläuft über das Halteproblem zu argumentieren habe ich mir schon gedacht. Deshalb habe ich ja die Hilfsfunktion definiert. Ich kann halt nur sagen, dass fk nicht berechenbar ist, da zur Berechnung das Halteproblem entscheidbar sein müsste. Es müsste also eine Funktion existieren, die Nein Antwortet, wenn M nicht mit Eingabe w hält. Gäbe es diese Funktion, wäre das Halteproblem co-semi-entscheidbar. Da allgemein bekannt ist, dass was Halteproblem semi entscheidbar ist, wäre es somit insgesamt entscheidbar. Hier haben wir also einen Widerspruch. Bei diesem Aufgabentypus fällt es mir immer sehr schwer, ausreichend zu begründen. Gefühlt kann ich hier 10 Dinge schreiben, aber was davon richtig ist, weiß ich immer erst, wenn es jemand korrigiert.


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2028
  Beitrag No.4, eingetragen 2021-07-18

Hallo Schutze, ihr müsst doch in der Vorlesung die Reduzierbarkeit eines Problems auf ein anderes definiert haben. Wie sieht die aus? Für eine saubere Begründung musst du dich an dieser Definition orientieren. Du schreibst: "Ich kann halt nur sagen, dass fk nicht berechenbar ist, da zur Berechnung das Halteproblem entscheidbar sein müsste." - Aber genau das kannst Du á priori nicht sagen. Du brauchst vielmehr einen Beweis der Umkehrung: Wenn $f_k$ berechenbar ist, mit welchem Algorithmus kannst Du damit dann das Halteproblem lösen? Viele Grüße Thorsten


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.5, vom Themenstarter, eingetragen 2021-07-18

Wenn ich mich recht entsinne, haben wir die Reduktion erst mit NP-vollständigkeits Beweisen eingeführt. Da waren wir mit der Berechenbarkeit bereits durch. Wie ich das Prinzip hier anwenden soll ist mir nicht ganz klar. Ich versuche es dann nochmal. Angenommen fk ist berechenbar. Dann existiert ein Algorithmus A, mit A(M(w)):= {1,falls M(w) hält und 0 sonst Dieser wird für die Berechnung von fk |W| mal ausgeführt und die positiven Ergebnisse werden aufsummiert. Würde dieser Algorithmus existieren, könnten wir ihn nutzen, um das Halteproblem zu lösen. -> Widerspruch


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2028
  Beitrag No.6, eingetragen 2021-07-18

Hallo Schutze, \quoteon(2021-07-18 13:12 - Schutze in Beitrag No. 5) Angenommen fk ist berechenbar. Dann existiert ein Algorithmus A, mit A(M(w)):= {1,falls M(w) hält und 0 sonst Dieser wird für die Berechnung von fk |W| mal ausgeführt und die positiven Ergebnisse werden aufsummiert. \quoteoff Auch dieser Schluss ist leider wieder nicht zulässig. Alles, was man weiß, ist dass ein Algorithmus existiert mit $A(\left\langle M \right \rangle)$ = Anzahl haltender Rechnungen von $M$ auf Eingabewörtern der Länge $k$. Dabei bezeichne ich mit $\left\langle M \right \rangle$ die Kodierung der Maschine $M$. Man darf sich nicht überlegen, wie dieser Algorithmus $A$ funktioniert (wie Du es versucht hast, indem Du ihn aus "Teilalgorithmen" zusammensetzen wolltest), sondern muss ihn einfach als Blackbox hinnehmen. Dann versucht man diesen Algorithmus zu nehmen, um das Halteproblem damit zu lösen. Das lässt sich z.B. so argumentieren: Um zu entscheiden, ob eine Rechnung $M(w)$ hält, konstruiert man eine hilfsweise Maschine $M'$, die sich bei jeder Eingabe so verhält wie $M$ bei Eingabe $w$, d.h. $M'(w') = M(w)$ für alle $w' \in \Sigma^\ast$. Was kannst Du nun über $A(\left\langle M' \right\rangle)$ sagen? Viele Grüße Thorsten


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.7, vom Themenstarter, eingetragen 2021-07-18

Wenn wir alle w aus Sigma* betrachten, würde A ja dann niemals terminieren, weil wir keine endliche Sprache prüfen. Die Erleuchtung kommt mir vermutlich auch nicht mehr über Nacht, aber danke für deine Zeit und Mühe.


   Profil
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2028
  Beitrag No.8, eingetragen 2021-07-19

Hallo Schutze, ich verstehe nicht, was Du meinst. Natürlich terminiert A, das ist ja die Bedingung an diesen Algorithmus, da er $f_k$ berechnen soll. Um das Argument mal noch selbst zu vervollständigen: Es gilt dann: $M(w) \text{ hält}$ $\Rightarrow M'(w') \text{ hält für alle } w' \in \Sigma^\ast$ $\Rightarrow M'(w') \text{ hält für alle } w' \in \Sigma^k$ $\Rightarrow f_k(M') = 2^k$ $(\Rightarrow$ $A(\left\langle M' \right\rangle) = 2^k$). Und: $M(w) \text{ hält nicht}$ $\Rightarrow M'(w') \text{ hält für kein } w' \in \Sigma^\ast$ $\Rightarrow M'(w') \text{ hält für kein } w' \in \Sigma^k$ $\Rightarrow f_k(M') = 0$ $(\Rightarrow$ $A(\left\langle M' \right\rangle) = 0$). Also zusammengefasst: $M(w) \text{ hält } \Leftrightarrow f_k(\left\langle M' \right\rangle) = 2^k$. Und damit hat Dir die Funktion $f_k$ geholfen, das Halteproblem zu entscheiden. Kannst Du diesen Beweis zumindest nachvollziehen? Viele Grüße Thorsten


   Profil
Schutze hat die Antworten auf ihre/seine Frage gesehen.

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-2021 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]