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
id UNACIONAL2_8f522a97c46044770764d087e5b0fa08
oai_identifier_str oai:repositorio.unal.edu.co:unal/31660
network_acronym_str UNACIONAL2
network_name_str Universidad Nacional de Colombia
repository_id_str
spelling Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2De Castro, Rodrigodd2d8603-9012-4a14-bc71-c43aa86a7c3e3002019-06-26T14:41:31Z2019-06-26T14:41:31Z1997https://repositorio.unal.edu.co/handle/unal/31660http://bdigital.unal.edu.co/21739/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 .It is shown that some recursion schemes can be carried out in the second order theories of Bounded Arithmetic U2i ( i  ≥1) introduced by S. Buss in [2]. In particular, we prove that the class of  ∑11,b - definable functions in U2i is closed under bounded recursion, or, equivalently, that U2i can  ∑11,b - define the functions in the second class of Grzegorczyk, E2 .application/pdfspaBoletín de Matemáticashttp://revistas.unal.edu.co/index.php/bolma/article/view/18245Universidad Nacional de Colombia Revistas electrónicas UN Boletín de MatemáticasBoletín de MatemáticasBoletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 2357-6529 0120-0380De Castro, Rodrigo (1997) Recursion in second order bounded arithmetic. Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 2357-6529 0120-0380 .Recursion in second order bounded arithmeticArtículo de revistainfo:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/ARTbounded Arithmeticsecond order theoriesbounded recursionGrzegorczyk classesaritmética acotada de segundo ordenrecursión acotadasegunda clase GrzegorczykORIGINAL18245-59032-1-PB.pdfapplication/pdf1557416https://repositorio.unal.edu.co/bitstream/unal/31660/1/18245-59032-1-PB.pdf11540ee5ee520e1ae91f22507b7f9102MD51THUMBNAIL18245-59032-1-PB.pdf.jpg18245-59032-1-PB.pdf.jpgGenerated Thumbnailimage/jpeg2370https://repositorio.unal.edu.co/bitstream/unal/31660/2/18245-59032-1-PB.pdf.jpg2813a55ab9e5beca67a4ef45a58137c6MD52unal/31660oai:repositorio.unal.edu.co:unal/316602022-12-02 23:05:30.198Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co
dc.title.spa.fl_str_mv Recursion in second order bounded arithmetic
title Recursion in second order bounded arithmetic
spellingShingle Recursion in second order bounded arithmetic
bounded Arithmetic
second order theories
bounded recursion
Grzegorczyk classes
aritmética acotada de segundo orden
recursión acotada
segunda clase Grzegorczyk
title_short Recursion in second order bounded arithmetic
title_full Recursion in second order bounded arithmetic
title_fullStr Recursion in second order bounded arithmetic
title_full_unstemmed Recursion in second order bounded arithmetic
title_sort Recursion in second order bounded arithmetic
dc.creator.fl_str_mv De Castro, Rodrigo
dc.contributor.author.spa.fl_str_mv De Castro, Rodrigo
dc.subject.proposal.spa.fl_str_mv bounded Arithmetic
second order theories
bounded recursion
Grzegorczyk classes
aritmética acotada de segundo orden
recursión acotada
segunda clase Grzegorczyk
topic bounded Arithmetic
second order theories
bounded recursion
Grzegorczyk classes
aritmética acotada de segundo orden
recursión acotada
segunda clase Grzegorczyk
description 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 .
publishDate 1997
dc.date.issued.spa.fl_str_mv 1997
dc.date.accessioned.spa.fl_str_mv 2019-06-26T14:41:31Z
dc.date.available.spa.fl_str_mv 2019-06-26T14:41:31Z
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.coarversion.spa.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/ART
format http://purl.org/coar/resource_type/c_6501
status_str publishedVersion
dc.identifier.uri.none.fl_str_mv https://repositorio.unal.edu.co/handle/unal/31660
dc.identifier.eprints.spa.fl_str_mv http://bdigital.unal.edu.co/21739/
url https://repositorio.unal.edu.co/handle/unal/31660
http://bdigital.unal.edu.co/21739/
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.spa.fl_str_mv http://revistas.unal.edu.co/index.php/bolma/article/view/18245
dc.relation.ispartof.spa.fl_str_mv Universidad Nacional de Colombia Revistas electrónicas UN Boletín de Matemáticas
Boletín de Matemáticas
dc.relation.ispartofseries.none.fl_str_mv Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 2357-6529 0120-0380
dc.relation.references.spa.fl_str_mv De Castro, Rodrigo (1997) Recursion in second order bounded arithmetic. Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 Boletín de Matemáticas; Vol. 4, núm. 2 (1997); 73-84 2357-6529 0120-0380 .
dc.rights.spa.fl_str_mv Derechos reservados - Universidad Nacional de Colombia
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.license.spa.fl_str_mv Atribución-NoComercial 4.0 Internacional
dc.rights.uri.spa.fl_str_mv http://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
rights_invalid_str_mv Atribución-NoComercial 4.0 Internacional
Derechos reservados - Universidad Nacional de Colombia
http://creativecommons.org/licenses/by-nc/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Boletín de Matemáticas
institution Universidad Nacional de Colombia
bitstream.url.fl_str_mv https://repositorio.unal.edu.co/bitstream/unal/31660/1/18245-59032-1-PB.pdf
https://repositorio.unal.edu.co/bitstream/unal/31660/2/18245-59032-1-PB.pdf.jpg
bitstream.checksum.fl_str_mv 11540ee5ee520e1ae91f22507b7f9102
2813a55ab9e5beca67a4ef45a58137c6
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad Nacional de Colombia
repository.mail.fl_str_mv repositorio_nal@unal.edu.co
_version_ 1814089206654304256

Publicaciones similares