[FOM] inconsistency of P

Harvey Friedman friedman at math.ohio-state.edu
Sun Oct 2 19:47:52 EDT 2011


> On Oct 1, 2011, at 8:36 AM, Edward Nelson wrote:
>
> Terrence Tao, at
> http://golem.ph.utexas.edu/category/2011/09/
> and independently Daniel Tausk (private communication)
> have found an irreparable error in my outline.
> In the Kritchman-Raz proof, there is a low complexity
> proof of K(\bar\xi)>\ell if we assume \mu=1, but the
> Chaitin machine may find a shorter proof of high
> complexity, with no control over how high.
>
> My thanks to Tao and Tausk for spotting this.
> I withdraw my claim.
>
> The consistency of P remains an open problem.

Ed - you indicated earlier that the "proof" was checked in a proof  
verifier.

Can you explain how this incorrect proof passed through (?) a proof  
verifier, and also explain more about the nature of this proof  
verifier and your experience with it?

I also reiterate my question in http://www.cs.nyu.edu/pipermail/fom/2011-October/015833.html

Harvey Friedman


More information about the FOM mailing list