Computability in Europe 2008
Logic and Theory of Algorithms
|Speaker:||Michiel De Smet|
|Author(s):||Michiel De Smet and Andreas Weiermann|
|Slot:||Wed, 11:50-12:10, Amphitheater A (col. 1)|
Motivated by the classical Ramsey for pairs problem in reverse mathematics we investigate the recursion-theoretic complexity of certain assertions which are related to the Erdös-Szekeres theorem. We show that resulting density principles give rise to Ackermannian growth. We then parameterize these assertions with respect to a number-theoretic function f and investigate for which functions f Ackermannian growth is still preserved. We show that this is the case for f(i) = sqrt[d](i) but not for f(i) = log(i).
|websites: Arnold Beckmann||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136