Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Third-Order Computation and Bounded Arithmetic


Speaker: Alan Skelley
Author(s): Alan Skelley
Slot: Array, 10:50-11:10, col. 2

Abstract

We describe a natural generalization of ordinary computation to a
third-order setting and give a function calculus with nice properties
and recursion-theoretic characterizations of several large complexity
classes.  We then present a number of third-order theories of bounded
arithmetic whose definable functions are the classes of the EXP-time
hierarchy in the third-order setting. 


websites: Arnold Beckmann 2006-04-29