SUBRECURSIVE HIERARCHIES AND PROVABLY COMPUTABLE FUNCTIONS IN FORMAL THEORIES OF ARITHMETIC
Noriya Kadota · Hiroshima University Acedemic Information Repository (Hiroshima University) · 2014
CONTENTS CHAPTER1 INTRODUCTION / p1 CHAPTER2 SUBRECURSIVE HIERARCHIES AND FORMAL THEORIES / p8 2.1 Fast-growing hierarchy / p8 2.2 Provable computability / p13 2.3 Undecidable statements / p16 CHAPTER3 BUILT-UP SYSTEMS OF FUNDAMENTAL SEQUENCES / p19 3.1 Growing hierarchies on (n)-built-up systems / p19 3.2 Conditions on systems of fundamental sequences / p25 3.3 Existence problems / p29 CHAPTER4 PROVABLY COMPUTABLE FUNCTIONS IN PEANO ARITHMETIC / p34 4.1 Provable computability / p34 4.2 Undecidable combinatorial statements / p40 4.3 Relativized hierarchies / p44 CHAPTER5 THE FAST AND SLOW GROWING HIERARCHIES AND INDUCTIVE DEFINITIONS / p50 5.1 Fast-growing versus slow-growing / p50 5.2 The collapsing theorem and (3)-built-upness / p55 5.3 Provable computability / p61 CHAPTER6 DISCUSSIONS / p69 6.1 Undecidable statements in theories of arithmetic / p69 6.2 Applications of subrecursive hierarchies / p71 ACKNOWLEDGMENTS / p75 REFERENCES / p76