FOM: determinate truth values, coherent pragmatism

Harvey Friedman friedman at
Thu Sep 7 15:11:59 EDT 2000

Reply to Kanovei 6:52Pm 9/7/00:

>>Date: Tue, 5 Sep 2000 12:02:04
>>From: Harvey Friedman <friedman at>
>>On the other hand, we already know how to meet the following challenge by
>>the statistical method of repeated trials:
>>CHALLENGE 3. Find a way to confirm or reject a Pi-0-1 sentence of the form
>>"for most bit strings of length at most 1000, such and such feasibly
>>testable property holds" other than finding a proof or refutation of that
>>statement from accepted axioms.
>Can you make it more clear what do you mean by
>"other than finding a proof ... from accepted axioms" ?
>Well, in some cases you can execute a computation that
>results in 0 or 1 and you interpret this as TRUE or FALSE
>(a given sentence is).
>Then (in fact, before) you have to demonstrate that this is
>just a true answer, which cannot be anything other than a
>mathematically rigorous "proof from accepted axioms", whatever
>simple set of axioms is sufficient for such a demonstration.

This is the so called Monte Carlo "proof" which is not rigorous. Using a
physically constructed random bit generator generate a very large number of
"random" samples of bit strings of length at most 1000 (the space can be
taken to be the bit strings of length exactly 1001). Observe that at least,
say, 51% of the bit strings has the feasibly testable property. This
confirms that more than 50% of the bit strings actually have the property.
This is an accepted and reliable principle of confirmation, but is not
formally rigorous in the usual sense.

More information about the FOM mailing list