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...
- 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
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 . |
---|