私はアルゴリズムを勉強していて、この演習に出くわしました:
「プログラム P が与えられた入力 x で初期化されていない変数を使用するかどうかを決定するプログラム/アルゴリズムがないことを証明してください。」
これが私が思いついた証拠です：
プログラム P が特定の入力 x で初期化されていない変数を使用しているかどうかを判断するアルゴリズム Det があると仮定しましょう。
プログラムを
P(x) Det(P,x) が true の場合、何もしません variable i print i
ここに矛盾が見られます。Det(P,x) が false の場合、初期化されていない変数が使用されています。初期化されていない変数を他の場所で使用していないため、true を返すたびに間違っています。
正しい方法で考えているかどうかはわかりません。
あなたはほとんどそれを持っていると思いますが、真に矛盾を示すにはもう少し言わなければなりません.
あなたのプログラムは完璧です。つまり、「P(x): Det(P,x) が true の場合は、他に何もしません。変数 i は i を出力します」。Det(P,x) が false と評価されるケースも示されましたが、Det(P,x) が true と評価された場合に何が起こるかについて言及するのを忘れていました (このケースは完全を期すために必要です)。例えば：
Det(P,x) が真であると仮定します。次に、Det は、P(x) が入力 x で初期化されていない変数を使用していると判断しました。しかし、P は、Det(P,x) が true の場合、初期化されていない変数を使用しないと述べているため、これは不可能です。
ここで、Det(P,x) が false であるとします。次に、Det は、P(x) が初期化されていない変数を使用していないと判断しました。しかし、P は、Det(P,x) が true の場合、初期化されていない変数 i を使用すると述べているため、これは不可能です。
したがって、Det(P,x) を評価すると常に矛盾が生じ、存在できないことを意味します。
編集: この証明は正しくありません! Det(P,x) は P を検査するだけであり、Det(P,x) が自分自身への呼び出しを検出した場合、Det(P,x) は初期化されていない変数を使用することを選択し、true を返します。現在、正しい解決策を見つけようとしています (コメントを参照)。