Description
The lecture introduces the concepts of computation under bounded resources.
The theory of computability as developed at the beginning of the last century lies at the very heart of computer science. Computations, where the resources are limited, can be conceived as investigations into computational complexity theory. On the other hand computations with bounded resources have also been intensively studied in the area of program analysis, as program analysis offers techniques for predicting the behaviour of programs.
While traditionally these two conceptions of computation with limited resources are studied in quite separate communities, our research aims to unify the approaches to get the best of both worlds. The methodology used for this are investigations into the logical foundations of the nature of computation (with bounded resources) and (automated) resource analysis of programs.
In the lecture we review our current research on computation under bounded resources.
Additional Material
Why Ordinals are Good for You Ingo Lepper and Georg Moser. ESSLLI 2003 - Course Material III, pages 1 – 70, 2003