Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-09T09:38:37.717Z Has data issue: false hasContentIssue false
  • English
  • Français

Extensions of arithmetic for proving termination of computations

Published online by Cambridge University Press:  12 March 2014

Clement F. Kent  and
Bernard R. Hodgson
Clement F. Kent
Affiliation:
Department of Mathematical Sciences, Lakehead University, Thunder Bay, Ontario P7B 5E1, Canada
Bernard R. Hodgson
Affiliation:
Département de Mathématiques et de Statistique, Université Laval, Québec G1K 7P4, Canada
Get access Rights & Permissions [Opens in a new window]

Abstract

Kirby and Paris have exhibited combinatorial algorithms whose computations always terminate, but for which termination is not provable in elementary arithmetic. However, termination of these computations can be proved by adding an axiom first introduced by Goodstein in 1944. Our purpose is to investigate this axiom of Goodstein, and some of its variants, and to show that these are potentially adequate to prove termination of computations of a wide class of algorithms. We prove that many variations of Goodstein's axiom are equivalent, over elementary arithmetic, and contrast these results with those recently obtained for Kruskal's theorem.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 54 , Issue 3 , September 1989 , pp. 779 - 794
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

[BW87]Buchholz, W. and Wainer, S., Provably computable functions and the fast growing hierarchy, in [Si87], pp. 179–198.CrossRefGoogle Scholar
[Ci83]Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proceedings of the American Mathematical Society, vol. 87 (1983), pp. 704–706.CrossRefGoogle Scholar
[De87]Dershowitz, N., Termination of rewriting, Journal of Symbolic Computation, vol. 3 (1987), pp. 69–115.CrossRefGoogle Scholar
[DM79]Dershowitz, N. and Manna, Z., Proving termination with multiset ordering, Communications of the Association for Computing Machinery, vol. 22 (1979), pp. 465–476.CrossRefGoogle Scholar
[F167]Floyd, R. W., Assigning meanings to programs, Mathematical aspects of computer science, Proceedings of Symposia in Applied Mathematics, vol. 19, American Mathematical Society, Providence, Rhode Island, 1967, pp. 19–32.CrossRefGoogle Scholar
[Go44]Goodstein, R. L., On the restricted ordinal theorem, this Journal, vol. 9 (1944), pp. 33–41.Google Scholar
[KP82]Kirby, L. and Paris, J., Accessible independence results for Peano arithmetic, Bulletin of the London Mathematical Society, vol. 14 (1982), pp. 285–293.CrossRefGoogle Scholar
[LM87]Loebl, M. and Matoušek, J., On undecidability of the weakened Kruskal theorem, in [Si87], pp. 275–280.CrossRefGoogle Scholar
[Ma74]Manna, Z., Mathematical theory of computation, McGraw-Hill, New York, 1974.Google Scholar
[Ma80]Manna, Z., Lectures on the logic of computer programming, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1980.CrossRefGoogle Scholar
[Mi85]Mili, A., An introduction to formal program verification, Van Nostrand, New York, 1985.Google Scholar
[Sc77]Schwichtenberg, H., Proof theory: some applications of cut elimination, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, 1977, pp. 867–895.CrossRefGoogle Scholar
[Si87]Simpson, S. G. (editor), Logic and combinatorics (Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, August 1985), Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, Rhode Island, 1987.CrossRefGoogle Scholar