• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Polynomially Bounded Recursive Realizability

Saeed Salehi, Polynomially Bounded Recursive Realizability. Notre Dame Journal of Formal Logic 46(4), 407 – 417, 2005.

Abstract:

A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is inconsistent with Heyting Arithmetic.

BibTeX entry:

@ARTICLE{jSalehi05c,
  title = {Polynomially Bounded Recursive Realizability},
  author = {Salehi, Saeed},
  journal = {Notre Dame Journal of Formal Logic},
  volume = {46},
  number = {4},
  pages = {407 – 417},
  year = {2005},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication