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


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