David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 54 (3):779-794 (1989)
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
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Andreas Weiermann (2005). Analytic Combinatorics, Proof-Theoretic Ordinals, and Phase Transitions for Independence Results. Annals of Pure and Applied Logic 136 (1):189-218.
Similar books and articles
Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. Journal of Logic, Language and Information 14 (2):133-148.
C. Ward Henson, Matt Kaufmann & H. Jerome Keisler (1984). The Strength of Nonstandard Methods in Arithmetic. Journal of Symbolic Logic 49 (4):1039-1058.
Grigori Mints (1996). Strong Termination for the Epsilon Substitution Method. Journal of Symbolic Logic 61 (4):1193-1205.
Dan E. Willard (2002). How to Extend the Semantic Tableaux and Cut-Free Versions of the Second Incompleteness Theorem Almost to Robinson's Arithmetic Q. Journal of Symbolic Logic 67 (1):465-496.
Added to index2009-01-28
Total downloads8 ( #159,177 of 1,096,320 )
Recent downloads (6 months)6 ( #32,806 of 1,096,320 )
How can I increase my downloads?