3 ms·
For 1., the fact that the program searches for a proof of a statement is completely irrelevant. It might just as well search for a string that can be appended t
by yorwba 10y ago
For 1., the fact that the program searches for a proof of a statement is completely irrelevant. It might just as well search for a string that can be appended to the statement to make it MD5-hash to a prime number.
In any case, either it finds such a thing, in which case it accepts the finite set in the statement, or it doesn't find anything, in which case it accepts the (finite) empty set.
The actual condition doesn't matter, PA can always do this kind of case analysis to prove the finiteness of the accepted set.
- amluto 10y agoI still don't get it. The finitely many input part is irrelevant. Suppose we have a program that either produces a valid PA proof of a sentence P or fails to do so. Suppose further that, if the program failed to do so, it was obvious that P was true. This implies that P is true, but how would PA prove that? In the case in the article, P is "e accepts such-and-such".
- yorwba 10y agoThe claim is not that P is true. P is "e does not accept exactly {n_1, ..., n_k}". If it produces a proof, it accepts exactly {n_1, ..., n_k}, which is precisely the opposite of P. If we limit ourselves to the standard model, this program will never terminate, because it tries to prove a false statement. In a nonstandard model, the program may succeed after a nonstandard "number" of steps to find a nonstandard "proof" of a false statement, after which it terminates by accepting the opposite of what the "proof" says it does. Anyway, what exactly the program does before it accepts anything is actually irrelevant for point 1, which is only about the number of accepted inputs being finite. For that, you only have to look at the last steps, which only accept for a finite number of runs, even those that can never happen in the standard model.