Article contents
Complexity bounds on proofs
Published online by Cambridge University Press: 12 March 2014
Extract
In a recent article in this Journal (see [3]), J.P. Jones states and proves a theorem which purports to give an “absolute epistemological upper bound on the complexity of mathematical proofs” for recursively axiomatizable theories. However, Jones' statement of this result is misleading, and in fact defective, as can be seen by a close analysis of it. Such an analysis is the object of the present note.
The main point is that Jones' “epistemological bound” can in no way be considered a computational bound on the complexity of proofs. Not only is the “proof-theoretic interpretation of the number 243” contained in Jones' article objectionable but, more fundamentally, there is in a strong sense no way one can hope to recover anything like the full force suggested by Jones' original statement of the theorem.
We wish to insist that our comments concern only the difficulties surrounding Jones' Corollary 1 on p. 338 of his article and not his ingenious construction of universal Diophantine representations of r.e. sets presented in the same article.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1981
References
REFERENCES
- 3
- Cited by