Title
Semantics vs. Syntax vs. Computations: Machine models for type-2 polynomial-time bounded functionals
Document Type
Article
Date
1997
Keywords
Kreisel-Lacombe-Shoenfield Theorem, polynomial-time functionals, polynomial-time effective operations
Language
English
Disciplines
Computer Sciences
Description/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 R (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 R.
Recommended Citation
Royer, James S., "Semantics vs. Syntax vs. Computations: Machine models for type-2 polynomial-time bounded functionals" (1997). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 19.
https://surface.syr.edu/lcsmith_other/19
