[FOM] Checkers is a draw

John McCarthy jmc at cs.Stanford.EDU
Sun Jul 29 21:11:41 EDT 2007

Timothy Chow quotes Neelakantan Krishnaswami as saying in part

> To understand why this sort of rule is necessary, consider the example
> of showing that 170 * 40 = 6800. No one will do this proof by
> appealing to Peano's axioms, because it would be thousands of lines
> long. Instead we will /calculate/ that 170 * 40 gives 6800, and then
> appeal to reflexivity, which is a one-line proof plus some
> computation.

I agree that reflexivity and appealing to the computer is the best way
to go.  However, a proof from Peano's axioms expressed in first order
logic that 170 * 40 = 6800 need not be thousands of lines provided
some definitions and theorems expressing the grade school way of doing
the calculation are provided.  If this is done, the size of the proof
of a particular multiplication will be a small multiple of the size of
the calculation


As far as I can see, calculations can always be replaced by proofs at
the cost of a small multiple of size plus and additive constant for
definitions and theorems.  However, I do not see any advantage in
avoiding reflection principles.

More information about the FOM mailing list