Logical Approaches to Computational Barriers

Some Results on Local LR-degree Structures

Speaker:
| Anthony Morphett |

Slot: |
Array, 11:20-11:40, col. 3 |

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 | 2008-05-19 |