This logic stuff is pretty tricky, but I’ll try to explain how exactly the distinction between truth and provability matters in this problem. It was quite an epiphany when it hit me.
The first proposition indeed holds for every program. But it is not what is used to show that A returns 1. What is really used is this: A can prove that the first proposition holds for A by looking at the source code of A. This is definitely not the case for every program! (Provability-of-provability does not imply provability-of-truth. This is the whole point of Löb’s Theorem.) A’s proof of the first proposition relies on how the code of A looks—specifically, that it says explicitly “if provable then return 1”. This proof would break if the structure of A were changed. For example, if A were searching for both proofs and disproofs that it would output 1, it wouldn’t be able to prove the first proposition quite so easily, and maybe not at all.
Well, my proof is basically a rewrite of Eliezer’s proof in another notation and with tracking of proof lengths. The exact same steps in the exact same sequence. Even the name of the “box” statement is taken from there. So you can try, yeah.
For example, if A were searching for both proofs and disproofs that it would output 1, it wouldn’t be able to prove the first proposition quite so easily, and maybe not at all.
Yeah—I suspect the answer is “not at all” because this ‘searching for proofs or disproofs’ seems to be exactly what’s needed to unbreak the reasoning in my comment above.
...Nope.
This logic stuff is pretty tricky, but I’ll try to explain how exactly the distinction between truth and provability matters in this problem. It was quite an epiphany when it hit me.
The first proposition indeed holds for every program. But it is not what is used to show that A returns 1. What is really used is this: A can prove that the first proposition holds for A by looking at the source code of A. This is definitely not the case for every program! (Provability-of-provability does not imply provability-of-truth. This is the whole point of Löb’s Theorem.) A’s proof of the first proposition relies on how the code of A looks—specifically, that it says explicitly “if provable then return 1”. This proof would break if the structure of A were changed. For example, if A were searching for both proofs and disproofs that it would output 1, it wouldn’t be able to prove the first proposition quite so easily, and maybe not at all.
I’m still confused, sadly.
Can you follow Eliezer’s cartoon proof of Löb’s Theorem, linked from the post? It’s kind of a prerequisite to understand what’s happening here.
I believe follow Eliezer’s proof—should I look over your proof again?
Well, my proof is basically a rewrite of Eliezer’s proof in another notation and with tracking of proof lengths. The exact same steps in the exact same sequence. Even the name of the “box” statement is taken from there. So you can try, yeah.
Yeah—I suspect the answer is “not at all” because this ‘searching for proofs or disproofs’ seems to be exactly what’s needed to unbreak the reasoning in my comment above.