File:	cs-92-264.ps.Z
Title:	Predicative Recursion and Computational Complexity
Author:	S. Bellantoni
Abstract:
The purpose of this thesis is to give a ``foundational'' characterization
of some common complexity classes. Such a characterization is distinguished
by the fact that no explicit resource bounds are used.  For example, I 
characterize the polynomial time computable functions without making any 
direct reference to polynomials, time, or even computation. Complexity 
classes characterized in this way include polynomial time, the polytime 
hierarchy, the logspace decidable problems, and NC. 

After developing these ``resource free'' definitions, I apply them to
redeveloping the feasible logical system of Cook and Urquhart, and show 
how this first-order system relates to the second-order system of Leivant.
The connection is an interesting one since the systems were defined
independently and have what appear to be very different rules for the 
principle of induction. Furthermore it is interesting to see, albeit in a 
very specific context, how to retract a second order *statement*,
(``induction holds up to x''), into first order *type* information.

Based on this analysis I discuss the notion of ``functional impredicativity'', 
and introduce the idea of attributing impredicativity to certain specific 
integers, relative to a computation which is being performed or a proof 
which is being carried out.


File: higher-type-comput.ps.Z
Title:  Comments On Two Notions of Higher Type Computability
	April 1990 with Preface June 1994
Author: S. Bellantoni

ABSTRACT -- This manuscript, which is not intended for refereed publication,
discusses various concepts and definitions in higher type computability.
The body of the text is concerned with the relationship between Kleene's 
schemas S1-S10 circa 1958-62 and the Scott computable continuous functionals.
A preface, added later, discusses the relationship of Kleene's revised 
semantics circa 1980-85 to Scott computability. A conjecture is given for 
an updated version of the problem: what schemas should be added to the 
Kleene system in order to compute exactly the recursively countable 
functionals?