Die Gleichung xn + yn = zn hat für kein natürliches |
Unter einem universellen Halte-Tester versteht man einen Algorithmus, der zu jedem beliebigen Programm XYZ und jedem beliebigen Datensatz DAT nach endlich vielen Schritten entscheidet, ob XYZ bei Eingabe von DAT anhält oder nicht. |
Das Halte-Problem ist nicht entscheidbar, d.h. es gibt keinen Algorithmus, der nach endlich vielen Schritten entscheiden kann, ob ein beliebiger anderer Algorithmus für beliebige gegebenene Eingabedaten halten wird oder nicht. |
ELCH (XYZ, DAT) JABei dieser Ausgabe hätte XYZ den ELCH-Test bestanden, - wenn auch nur für die speziellen Eingabedaten DAT, aber immerhin! Wir können den Test ja mit anderen Datensätzen DET, DIT, DOT,..... wiederholen. Liefert ELCH immer "JA", dann wächst unser Vertrauen in das Programm XYZ. Wenn wir dann alle möglichen Eingabe-Datensätze durchprobiert haben und nie das Testergebnis "NEIN" aufgetaucht ist, können wir XYZ das Prädikat "endlosschleifen-frei" zuerkennen.
program KNILCH (P); var i, k : Integer; begin If ELCH (P, P) = "NEIN" then exit else begin i := 1; k := 0; While i <> 0 do Inc(k); end; end.
Jede gerade natürliche Zahl größer als 2 lässt sich als Summe zweier Primzahlen darstellen. |
ELCH (GOLDBACH, [ENTER])bringt's sofort an den Tag! Liefert er "JA", dann hält das Programm GOLDBACH an; mithin gibt es eine gerade natürliche Zahl, die nicht als Summe zweier Primzahlen darstellbar ist. In diesem Fall erweist sich die Goldbach'sche Vermutung also als falsch. Liefert der obige Aufruf hingegen "NEIN", dann hält GOLDBACH nie an, sucht also endlos nach einem Gegenbeispiel für die Goldbach'sche Vermutung - und wird keines finden. Also ist die GOLDBACH'sche Vermutung wahr. ELCH würde uns diese Information liefern, ohne dass wir die unendliche Laufzeit von GOLDBACH abwarten müssten!