Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Regular Talk: - Exploring the computational contribution of a non-constructive combinatorial principle
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Exploring the computational contribution of a non-constructive combinatorial principle

Edit abstract data


Notice: Use of undefined constant session - assumed 'session' in /srv/www/htdocs-cs/cie08/conf-code.php on line 440

Notice: Use of undefined constant slot - assumed 'slot' in /srv/www/htdocs-cs/cie08/conf-code.php on line 441

Notice: Use of undefined constant room - assumed 'room' in /srv/www/htdocs-cs/cie08/conf-code.php on line 442
Speaker: Trifon Trifonov
Author(s): Diana Ratiu and Trifon Trifonov
Slot: Mon, 11:20-11:40, Propylaia (col. 2)

Abstract

The use of classical logic for some combinatoric proofs, as for
Ramsey's theorem or Weak K??ig's Lemma, can be localized in the
Infinite Pigeon Hole (IPH) principle, stating that any infinite
sequence, which is finitely colored, has an infinite monochromatic
subsequence. In general, there is no computable functional producing
such an infinite subsequence. However, it is possible to extract a
program from a corollary proving the classical existence of a finite
monochromatic subsequence of any given length. We applied two methods
for extraction from classical proofs - the refined A-translation, as
proposed by Berger et al., and G??el's Dialectica interpretation. In
this talk we will compare the resulting programs and indicate how
they reflect the computational content of IPH.



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
2008-05-19 Valid HTML 4.01! Valid CSS!