Repositorio de producción científica de la Universidad de Sevilla

Local Induction and Provably Total Computable Functions: A Case Study

 

Advanced Search
 
Opened Access Local Induction and Provably Total Computable Functions: A Case Study
Cites

Show item statistics
Icon
Export to
Author: Cordón Franco, Andrés
Lara Martín, Francisco Félix
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2012
Published in: CiE 2012 : Turing Centenary Conference and 8th Conference on Computability in Europe (2012), p 440-449
ISBN/ISSN: 978-3-642-30869-7
0302-9743
Document type: Presentation
Abstract: Let IΠ−2 denote the fragment of Peano Arithmetic obtained by restricting the induction scheme to parameter free Π2 formulas. Answering a question of R. Kaye, L. Beklemishev showed that the provably total computable functions (p.t.c.f.) of IΠ−2 are, precisely, the primitive recursive ones. In this work we give a new proof of this fact through an analysis of the p.t.c.f. of certain local versions of induction principles closely related to IΠ−2 . This analysis is essentially based on the equivalence between local induction rules and restricted forms of iteration. In this way, we obtain a more direct answer to Kaye’s question, avoiding the metamathematical machinery (reflection principles, provability logic,...) needed for Beklemishev’s original proof.
Cite: Cordón Franco, A. y Lara Martín, F.F. (2012). Local Induction and Provably Total Computable Functions: A Case Study. En CiE 2012 : Turing Centenary Conference and 8th Conference on Computability in Europe (440-449), Cambridge, UK: Springer.
Size: 257.6Kb
Format: PDF

URI: https://hdl.handle.net/11441/87549

DOI: 10.1007/978-3-642-30870-3_45

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)