SEMANTICS VS SYNTAX VS COMPUTATIONS - MACHINE MODELS FOR TYPE-2 POLYNOMIAL-TIME BOUNDED FUNCTIONALS

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theo rem in the context of the type-2 basic feasible functionals. We develo p a direct, polynomial-time analog of effective operation in which the time bounding on computations is modeled after Kapron and Cook's sche me for their basic polynomial-time functionals. We show that if P = NP , these polynomial-time effective operations are strictly more powerfu l on R (the class of recursive functions) than the basic feasible func tions. We also consider a weaker notion of polynomial-time effective o peration where the machines computing these functionals have access to the computations of their procedural parameter, but not to its progra m 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. (C) 1997 Academic Press.