Ponencia
Local Induction and Provably Total Computable Functions: A Case Study
Autor/es | Cordón Franco, Andrés
Lara Martín, Francisco Félix |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2012 |
Fecha de depósito | 2019-06-24 |
Publicado en |
|
ISBN/ISSN | 978-3-642-30869-7 0302-9743 |
Resumen | 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 ... 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. |
Identificador del proyecto | MTM2008-06435 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Local Induction.pdf | 257.6Kb | [PDF] | Ver/ | |