dc.creator | Cordón Franco, Andrés | es |
dc.creator | Lara Martín, Francisco Félix | es |
dc.date.accessioned | 2019-06-24T08:48:52Z | |
dc.date.available | 2019-06-24T08:48:52Z | |
dc.date.issued | 2012 | |
dc.identifier.citation | 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. | |
dc.identifier.isbn | 978-3-642-30869-7 | es |
dc.identifier.issn | 0302-9743 | es |
dc.identifier.uri | https://hdl.handle.net/11441/87549 | |
dc.description.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. | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación MTM2008–06435 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Springer | es |
dc.relation.ispartof | CiE 2012 : Turing Centenary Conference and 8th Conference on Computability in Europe (2012), p 440-449 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Local Induction and Provably Total Computable Functions: A Case Study | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | MTM2008-06435 | es |
dc.relation.publisherversion | https://link.springer.com/chapter/10.1007%2F978-3-642-30870-3_45 | es |
dc.identifier.doi | 10.1007/978-3-642-30870-3_45 | es |
idus.format.extent | 10 | es |
dc.publication.initialPage | 440 | es |
dc.publication.endPage | 449 | es |
dc.eventtitle | CiE 2012 : Turing Centenary Conference and 8th Conference on Computability in Europe | es |
dc.eventinstitution | Cambridge, UK | es |
dc.relation.publicationplace | Berlin | es |