Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals

James S. Royer

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals. We develop a direct, polynomial-time analog of effective operation in which the time bounding on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that if P = NP, these polynomial-time effective operations are strictly more powerful on ℛ (the class of recursive functions) than the basic feasible functions. We also consider a weaker notion of polynomial-time effective operation where the machines computing these functionals have access to the computations of their procedural parameter, but not to its program text. For this version of polynomial-time effective operations, the analog of the Kreisel-Lacombe-Shoenfield is shown to hold - their power matches that of the basic feasible functionals on ℛ.

Original languageEnglish (US)
Pages (from-to)424-436
Number of pages13
JournalJournal of Computer and System Sciences
Volume54
Issue number3
DOIs
StatePublished - Jun 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Semantics vs Syntax vs Computations: Machine Models for Type-2 Polynomial-Time Bounded Functionals'. Together they form a unique fingerprint.

  • Cite this