Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Third-Order Computation and Bounded Arithmetic

Speaker: Alan Skelley
Author(s): Alan Skelley
Presentation: cie06slides.pdf
Slot: Tue, 10:50-11:10, Faraday B (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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net