Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T07:20:12.871Z Has data issue: false hasContentIssue false
  • English
  • Français

Two recursion theoretic characterizations of proof speed-ups

Published online by Cambridge University Press:  12 March 2014

James S. Royer
James S. Royer*
Affiliation:
Department of Computer Science, University of Chicago, Chicago, Illinois 60637
Get access Rights & Permissions [Opens in a new window]

Extract

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan (improving upon [Kle50] and [Kle52]) showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1 is speedable over another system S0 on a set of formulae A iff, for each recursive function h, there is a formula α in A such that the length of the shortest proof of α in S0 is larger than h of the shortest proof of α in S1. (Here we equate the length of a proof with something like the number of characters making it up, not its number of lines.) We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1 but unprovable in S0 from the collection A–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.

We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below, ϕ is an acceptable numbering of the partial recursive functions [Rog87] and Φ a (Blum) complexity measure associated with ϕ [Blu67], [DW83].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 2 , June 1989 , pp. 522 - 526
Copyright
Copyright © Association for Symbolic Logic 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Blu67]Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[CEF83]Case, J., K. Ebcioglu, and Fulk, M., R.e. inseparable general and subrecursive index sets, this Journal, vol. 48 (1983), 1235–1236.Google Scholar
[Di75]Paola, R. Di, A theorem on shortening the length of proof in formal systems of arithmetic, this Journal, vol. 40 (1975), pp. 398–400.Google Scholar
[DW83]Davis, M. and Weyuker, E., Computability, complexity, and languages, Academic Press, New York, 1983.Google Scholar
[EM71]Ehrenfeucht, A. and Mycielski, J., Abbreviating proofs by adding new axioms, Bulletin of the American Mathematical Society, vol. 77 (1971), pp. 366–367.CrossRefGoogle Scholar
[Göd36]Gödel, K., Über die Länge von Beweisen, Ergebnisse eines Mathematischen Kolloquiums, vol. 7 (1936), pp. 23–24; reprinted, with an English translation, in his Collected works. Vol. I, Oxford University Press, London, 1986, pp. 396–399.Google Scholar
[Har83]Hartmanis, J., On Gödel speed-up and succinctness of language representations, Theoretical Computer Science, vol. 26 (1983), pp. 335–342.CrossRefGoogle Scholar
[Kle50]Kleene, S., A symmetric form of Gödel's theorem, Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings of the Section of Sciences, vol. 53 (1950), pp. 800–802 = Indagationes Mathematical vol. 12 (1950), pp. 244–246.Google Scholar
[Kle52]Kleene, S., Introduction to metamathematics, Van Nostrand, Princeton, New Jersey, 1952.Google Scholar
[Mos52]Mostowski, A., Sentences undecidable in formalized arithmetic: an exposition of the theory of Kurt Gödel, North-Holland, Amsterdam, 1952.Google Scholar
[Par71]Parikh, R., Existence and feasibility in arithmetic, this Journal, vol. 36 (1971), pp. 494–508.Google Scholar
[Par73]Parikh, R., Some results on the length of proofs, Transactions of the American Mathematical Society, vol. 177 (1973), pp. 29–36.CrossRefGoogle Scholar
[Par86]Parikh, R., Introductory note to [Göd36], in Gödel, Kurt, Collected works, Vol. I, Oxford University Press, London, 1986, pp. 394–397.Google Scholar
[RC86]Royer, J. and Case, J., Progressions of relatively succinct programs in subrecursive hierarchies, Technical Report TR 86-007, Department of Computer Science, University of Chicago, Chicago, Illinois, 1986.Google Scholar
[Rog87]Rogers, H., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, Massachusetts, 1987.Google Scholar
[Smi85]Smith, R., The consistency strengths of some finite forms of the Higman and Kruskal theorems, Harvey Friedman's research on the foundations of mathematics (Harrington, L.et al., editors), North-Holland, Amsterdam, 1985, pp. 119–136.CrossRefGoogle Scholar
[Smu61]Smullyan, R., Theory of formal systems, Annals of Mathematics Studies, vol. 47, Princeton University Press, Princeton, New Jersey, 1961.CrossRefGoogle Scholar
[Soa87]Soare, R., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[Sta81]Statman, R., Speed-up by theories with infinite models, Proceedings of the American Mathematical Society, vol. 81 (1981), pp. 465–469.CrossRefGoogle Scholar