Generalizing cl-reducibility on left-c.e. reals

Date

The cl-reducibility is a Turing reducibility with use function bounded by $n+c$ where $c$ is a constant. For such reducibility, there is a Yu-Ding theorem saying that there is a pair of left-c.e. reals which are not both cl-reducible to any left-c.e. real, and a Barmpalias-Lewis theorem saying that there is a left-c.e. real which is not cl-reducible to any random left-c.e. real. Moreover, it is shown that both Yu-Ding theorem and Barmpalias-Lewis theorem characterize array computability for left-c.e. reals. A recently result shows that Yu-Ding theorem actually holds for a more generalized cl-reducibility where the use function is bounded by $n+h(n)$ where $h(n)$ is any nondecreasing slow-growing computable function with $\sum_n 2^{-h(n)} = \infty$. In this talk we examine the proof of Yu-Ding theorem from a new perspective in order to give a much simpler proof of the generalized Yu-Ding result and with the same framework we show that such generalization works for the Barmpalias-Lewis theorem as well. Moreover, the characterizations of array computability still hold under such generalization.