Trestone
Großmeister
- Registriert
- 12. April 2002
- Beiträge
- 883
Hallo,
mittels Stufenlogik (vgl. http://www.ask1.org/fortopic20575.html ) können ja die meisten indirekten Beweise umgangen werden,
für die Informatik ist das Halteproblem
( http://de.wikipedia.org/wiki/Halteproblem mit der These von Church im Umfeld)
ein berühmter solcher Beweis.
Ich möchte nun untersuchen, ob mittel der Stufenlogik neue Algorithmen (Metacomputer) beschrieben werden können,
für die das Halteproblem lösbar ist.
Klassisch sucht man ein Programm H(P, X), dass genau dann den Wert „w“ ausgibt,
wenn das Programm P bei Eingabestring X stoppt – und sonst „-w“ ausgibt.
Mit diesem Programm H könnte man folgendes Programm S konstruieren:
S(P):= if H(P,P)=w then “loop” else “-w”.
Damit wäre S(S) = if H(S,S)=w then “loop” else “-w”.
Also wenn S(S)=w dann S(S)= loop, wenn S(S) =-w dann S(S)=loop
und wenn S(S)=loop dann S(S)=-w, also stets ein Widerspruch analog zur Lügnerantinomie.
Da S bei existierendem H ein wohldefinierter Algorithmus wäre,
kann H klassisch nicht existieren, d.h. es gibt kein universelles Programm,
das das Halteproblem für alle Programme löst.
(Dabei werden die Programme als Turingprogramme oder z.B. Pascalprogramme
noch genauer spezifiziert.)
Nun betrachten wir das Ganze aus Sicht der Stufenlogik:
„H(P,X) gibt den Wert „w“ aus“ gilt hier nicht absolut, sondern bezogen auf eine Stufe,
ebenso wie die Eigenschaft „P(X) stoppt bei Eingabestring X“.
Da Eigenschaften einer Stufe nur in höheren bekannt sind, suchen wir also folgendes:
Ein Programm H, für das W ( H(P,X)=w , t+1 ) = w genau dann gilt,
wenn W( P(X) stoppt, t ) = w gilt und H = -w sonst.
Dann gilt für S: S(P) := if W(H(P,P)=w, t+1)=w then loop else –w
W(S(P)=?, d) ist erst für Stufe d>=t+2 entscheidbar.
Also W(S(S)=loop,t+2) = w wenn W(H(S,S)=w, t+1)=w , also wenn S(S) stoppt, t) = w
D.h. S loopt in t+2 wenn S in t stoppt (und umgekehrt).
Dies ist kein Widerspruch, da es sich um unterschiedliche Stufen handelt.
Also wäre ein Halteprogramm H noch möglich.
Zwar könnte es noch ein anderes Programm S geben, dass auf einen Widerspruch zu H führt,
aber die Stufenordnung macht dies zumindest unwahrscheinlich.
Benötigt wird allerdings eine Interpretation je Stufe, die bei gleichem Quelltext P und Eingabestring X
dennoch verschiedene Ausgabewerte zu P,X ermöglicht (wie bei S(S).).
Zusätzlich müssen die Algorithmen und insbesondere H endlich definierbar sein.
Dies kann z.B. durch (endliche) induktive bzw. reduktive Definition über t erfolgen.
Wenn wir so Algorithmen definieren könnten, wäre damit auch ein Metacomputer denkbar,
der auch Nicht-Turing-Programme abarbeitet und löst (und insbesondere das Halteproblem für Stufenprogramme).
Fall z.B. in Stufe 1 alle Turing-Programme enthalten wären, wäre ggf. sogar das Halteproplem für Turingprogramme (in Stufe 2) lösbar.
Bis zur praktischen Brauchbarkeit / Beweisbarkeit fehlen aber wohl noch einige Schritte …
Gruß
Trestone
mittels Stufenlogik (vgl. http://www.ask1.org/fortopic20575.html ) können ja die meisten indirekten Beweise umgangen werden,
für die Informatik ist das Halteproblem
( http://de.wikipedia.org/wiki/Halteproblem mit der These von Church im Umfeld)
ein berühmter solcher Beweis.
Ich möchte nun untersuchen, ob mittel der Stufenlogik neue Algorithmen (Metacomputer) beschrieben werden können,
für die das Halteproblem lösbar ist.
Klassisch sucht man ein Programm H(P, X), dass genau dann den Wert „w“ ausgibt,
wenn das Programm P bei Eingabestring X stoppt – und sonst „-w“ ausgibt.
Mit diesem Programm H könnte man folgendes Programm S konstruieren:
S(P):= if H(P,P)=w then “loop” else “-w”.
Damit wäre S(S) = if H(S,S)=w then “loop” else “-w”.
Also wenn S(S)=w dann S(S)= loop, wenn S(S) =-w dann S(S)=loop
und wenn S(S)=loop dann S(S)=-w, also stets ein Widerspruch analog zur Lügnerantinomie.
Da S bei existierendem H ein wohldefinierter Algorithmus wäre,
kann H klassisch nicht existieren, d.h. es gibt kein universelles Programm,
das das Halteproblem für alle Programme löst.
(Dabei werden die Programme als Turingprogramme oder z.B. Pascalprogramme
noch genauer spezifiziert.)
Nun betrachten wir das Ganze aus Sicht der Stufenlogik:
„H(P,X) gibt den Wert „w“ aus“ gilt hier nicht absolut, sondern bezogen auf eine Stufe,
ebenso wie die Eigenschaft „P(X) stoppt bei Eingabestring X“.
Da Eigenschaften einer Stufe nur in höheren bekannt sind, suchen wir also folgendes:
Ein Programm H, für das W ( H(P,X)=w , t+1 ) = w genau dann gilt,
wenn W( P(X) stoppt, t ) = w gilt und H = -w sonst.
Dann gilt für S: S(P) := if W(H(P,P)=w, t+1)=w then loop else –w
W(S(P)=?, d) ist erst für Stufe d>=t+2 entscheidbar.
Also W(S(S)=loop,t+2) = w wenn W(H(S,S)=w, t+1)=w , also wenn S(S) stoppt, t) = w
D.h. S loopt in t+2 wenn S in t stoppt (und umgekehrt).
Dies ist kein Widerspruch, da es sich um unterschiedliche Stufen handelt.
Also wäre ein Halteprogramm H noch möglich.
Zwar könnte es noch ein anderes Programm S geben, dass auf einen Widerspruch zu H führt,
aber die Stufenordnung macht dies zumindest unwahrscheinlich.
Benötigt wird allerdings eine Interpretation je Stufe, die bei gleichem Quelltext P und Eingabestring X
dennoch verschiedene Ausgabewerte zu P,X ermöglicht (wie bei S(S).).
Zusätzlich müssen die Algorithmen und insbesondere H endlich definierbar sein.
Dies kann z.B. durch (endliche) induktive bzw. reduktive Definition über t erfolgen.
Wenn wir so Algorithmen definieren könnten, wäre damit auch ein Metacomputer denkbar,
der auch Nicht-Turing-Programme abarbeitet und löst (und insbesondere das Halteproblem für Stufenprogramme).
Fall z.B. in Stufe 1 alle Turing-Programme enthalten wären, wäre ggf. sogar das Halteproplem für Turingprogramme (in Stufe 2) lösbar.
Bis zur praktischen Brauchbarkeit / Beweisbarkeit fehlen aber wohl noch einige Schritte …
Gruß
Trestone