Recursion in second order bounded arithmetic

Se muestra que algunos esquemas recursivos pueden ser ejecutados en las teorías U2i ( i ≥1) de aritmética acotada de segundo orden introducidas por S. Buss. En particular, se demuestra que la clase de las funciones ∑ 11,b - definibles en U2i es cerrada bajo recursión acotada, o, equivalentemente, qu...

Full description

Autores:
De Castro, Rodrigo
Tipo de recurso:
Article of journal
Fecha de publicación:
1997
Institución:
Universidad Nacional de Colombia
Repositorio:
Universidad Nacional de Colombia
Idioma:
spa
OAI Identifier:
oai:repositorio.unal.edu.co:unal/31660
Acceso en línea:
https://repositorio.unal.edu.co/handle/unal/31660
http://bdigital.unal.edu.co/21739/
Palabra clave:
bounded Arithmetic
second order theories
bounded recursion
Grzegorczyk classes
aritmética acotada de segundo orden
recursión acotada
segunda clase Grzegorczyk
Rights
openAccess
License
Atribución-NoComercial 4.0 Internacional
Description
Summary:Se muestra que algunos esquemas recursivos pueden ser ejecutados en las teorías U2i ( i ≥1) de aritmética acotada de segundo orden introducidas por S. Buss. En particular, se demuestra que la clase de las funciones ∑ 11,b - definibles en U2i es cerrada bajo recursión acotada, o, equivalentemente, que U2i  puede  ∑11,b - definir E2, la segunda clase de Grzegorczyk .