Herzlich Willkommen auf Weltverschwoerung.de

Angemeldete User sehen übrigens keine Werbung. Wir freuen uns wenn Du bei uns mitdiskutierst:

Halteproblem mit Meta-Algorithmus lösbar?

Trestone

Geheimer Meister
12. April 2002
306
Beim Informatikstudium lernte ich, dass das sogenannte Halteproblem unlösbar ist:
Es gibt keinen Algorithmus, der von allen Algorithmen entscheiden kann, ob sie bei einem beliebig gegebenen Startinput je stoppen.Insbesondere ließ sich dieser Satz für Turingprogramme (und alle heute bekannten Computerprogramme) beweisen.

Allerdings bleibt ein kleines Unbehagen, denn es handelt sich um einen Widerspruchsbeweis, den einige Mathematiker (z.B. Konstruktivisten?) nicht akzeptieren.

Außerdem sind Programme und Algorithmen kein Selbstzweck und werden von Menschen benutzt.

Stehe ich nun vor einem Programm P mit Input I, so möchte ich vielleicht wissen, ob P damit stoppt.
Nun frage ich mich, ob der Beweis des Halteproblems diese Situation überhaupt trifft. Denn dort gibt es nur Algorithmen und Programme - aber kein "ich" und seine Metaebene.

Könnte es nicht sein, dass es zu jedem Programm P und jedem Input I ein Halteprogramm M gibt, das zwar nicht unbedingt genau dann stoppt wenn P(I) das tut - aber an dem ich das Verhalten von P(I) doch sicher ablesen kann? Evtl. mit zusätzlichen Hypothesen über P(I) als Input?

Natürlich kann das Ein- bzw. Auslesen von Parametern nicht klassisch erfolgen (sonst könnten das Programme auch), aber als Menschen können wir z.B stets auf die Metaebene wechseln.

Solch ein kombinierter klassischer Algorithmus und Metaalgorithmus wäre vielleicht ziemlich leistungsstark?

Auf die Idee kam ich über meine Logikversuche, vgl. diesen Thread:
http://www.weltverschwoerung.de/modules.php?name=Forums&file=viewtopic&t=16058
 

Trestone

Geheimer Meister
12. April 2002
306
Ungeprüfte Idee für einen Meta-Computer/algorithmus/logik:

Die WENN - DANN - Beziehung wird über einen "Zauberspiegel" realisiert:

Wenn wir normale Aussagen im Spiegel betrachten, bleibt wahr wahr und falsch falsch.
Wenn wir paradoxe Aussagen betrachten, wird aus wahr beim Spiegeln falsch und aus falsch wahr.
Im Computer benötigen wir also bei allen IF-Abfragen noch ein Zauberspiegelelement,
das den THEN- bzw. ELSE-Fall passend ansteuert,
bei paradoxen IF-Bedingungen also genau invers zu herkömmlicher Logik.

Dies ist ein Meta-Element, da wohl kein herkömmlicher Algorithmus entscheiden kann,
welche Bedingungen paradox und welche klassisch sind.
Auch ich kann es zur Zeit nur für Einzelfälle, bin aber optimistisch, dass es fast menschenmöglich ist.
Noch schöner wäre ein Metaalgorithmus, der es kann, vielleicht aus "Elementarspiegelatomen"
wie der Lügnerbedingung L (Wenn wahr, dann falsch u. umgekehrt" aufgebaut.
Allerdings wird es wohl nicht ganz auf einem herkömmlichen Rechner umsetzbar sein,
da sonst nicht meta...
Vielleicht aber müssen wir nur die Interpretation von Ergebnissen und Speicherzuständen ändern. :roll:

Alles noch etwas unausgegoren, aber vielleicht regt es ja Dich? zum Forschen an? :!:
 
Ähnliche Beiträge
Verfasser Titel Forum Antworten Datum
somebody Der Meta Thread oder meine Ansichten sind das Nonplusultra Off-Topic 302

Ähnliche Beiträge

Oben Unten