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: - Some Results on Local LR-degree Structures
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Some Results on Local LR-degree Structures

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: Anthony Morphett
Slot: Tue, 11:20-11:40, Room 24 (col. 3)

Abstract

A natural direction of study arising from recent work in algorithmic
randomness is to investigate connections between the information
content of a set (in the sense of its Turing degree) and the notion
of relative randomness that is obtained by adding the set as an
oracle. One approach to this is the LR(low for random)-reducibility:
an set A is LR-reducible to B if the class of reals Martin-L"of
random relative to oracle B is contained in the class of randoms
relative to A. The associated degree structure is the LR-degrees. An
LR-degree is c.e. ($\Delta^0_2$ respectively) if it contains a c.e.
($\Delta^0_2$) set.

Although many questions exist about the global and local LR-degree
structures, some results have been obtained. For instance,
Barmpalias, Lewis and Soskova [2008] prove a splitting theorem for
c.e. sets, and Barmpalias, Lewis and Stephan [ta] prove a weak
density theorem for the c.e. LR-degrees. It is not known if full
density holds for the c.e. or $\Delta^0_2$ LR-degrees. We describe
some additional results about the c.e. and $\Delta^0_2$ LR-degrees,
including upward density results. We will also discuss some
similarities and differences between these structures and the c.e. or
$\Delta^0_2$ Turing degrees.


References:

George Barmpalias, Andrew E. M. Lewis, Mariya Soskova, Randomness,
Lowness and Degrees, Journal of Symbolic Logic vol.73, Issue 2, pp.
559-577 (2008)

George Barmpalias, Andrew E. M. Lewis, Frank Stephan, $\Pi^0_1$
classes, LR degrees and Turing degrees, to appear in Annals of Pure
and Applied Logic

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!