Beweisen kein solcher Algorithmus existiert

Question

I Algorithmen studiere und ich auf dieser Übung kam: ‚Zeigen Sie, dass es kein Programm/Algorithmus, der eine nicht initialisierte Variablen auf eine gegebene Eingabe x, wenn ein Programm P verwendet bestimmt‘

Hier

ist der Beweis, ich kam mit:

Nehmen wir an, dass es einen Algorithmus Det, um zu bestimmen, ob ein Programm P eine nicht initialisierte Variablen auf eine gegebene Eingabe x verwendet.

das Programm Let

P (x) wenn Det (P, x) tun nichts wahr ist sonst Variable i Druck i

Hier sehen wir einen Widerspruch. Wenn Det (P, x) falsch ist, haben wir eine nicht initialisierte Variable verwendet. Wir haben die nicht initialisierte Variable nicht an anderer Stelle verwendet, so dass sie immer falsch ist, wenn sie wahr ist.

Ich bin mir nicht sicher, ob ich richtig denke.

Answer 1

Ich denke, Sie haben es fast, aber Sie müssen ein bisschen mehr sagen, um den Widerspruch wirklich zu zeigen.

Ihr Programm ist perfekt, d. H. "P (x): wenn Det (P, x) wahr ist, tue nichts anderes Variable ich drucke i '. Sie haben auch den Fall gezeigt, in dem Det (P, x) zu false führt, aber Sie haben vergessen zu erwähnen, was passiert, wenn Det (P, x) als wahr auswertet (dieser Fall wird aus Gründen der Vollständigkeit benötigt). Zum Beispiel:

Angenommen, Det (P, x) ist wahr. Dann hat Det festgestellt, dass P (x) eine nicht initialisierte Variable mit der Eingabe x verwendet. Aber das ist unmöglich, da P angibt, dass, wenn Det (P, x) wahr ist, wir keine nicht initialisierte Variable verwenden.

Angenommen, Det (P, x) ist falsch. Dann hat Det festgestellt, dass P (x) keine nicht initialisierte Variable verwendet. Aber das ist unmöglich, da P sagt, dass, wenn Det (P, x) wahr ist, wir die nicht initialisierte Variable i verwenden.

Somit ergibt die Bewertung von Det (P, x) immer einen Widerspruch, was bedeutet, dass es nicht existieren kann.

BEARBEITEN: Dieser Beweis ist NICHT korrekt! Beachten Sie, dass Det (P, x) P nur untersuchen kann, und wenn Det (P, x) einen Aufruf an sich selbst sieht, dann wählt Det (P, x) eine nicht initialisierte Variable und gibt true zurück. Derzeit versuchen, eine korrekte Lösung zu finden (siehe Kommentare).