<> "The repository administrator has not yet configured an RDF license."^^ . <> . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals"^^ . "A real number is left-c.e.\\ if it has a left-c.e.\\ approximation, i.e., a computable nondecreasing sequence $a_0, a_1, ...$ of rationals that converges to the real number. Furthermore, a real number $\\alpha$ is Solovay reducible to a real number $\\beta$ if there exists a partially computable function~$g$ that maps every rational number~$q<\\beta$ to some rational number~$g(q)<\\alpha$ such that, for some real constant~$c$ and all~$q < \\beta$, it holds that\r\n\\[\r\n\\alpha - g(q) < c (\\beta - q) .\r\n\\]\r\nSolovay reducibility can be used to compare the speed at which left-c.e.\\ numbers can be approximated: if a real number~$\\alpha$ is Solovay reducible to a left-c.e.\\ real number~$\\beta$, then also~$\\alpha$ is left-c.e.\\ and, for every left-c.e.\\ approximation of~$\\beta$, there is a left-c.e.\\ approximation of~$\\alpha$ that converges at least as fast up to a constant factor.\r\n\r\nAmong the left-c.e.\\ reals, the Martin-Löf random ones have been intensively studied, and it is known that they have several natural equivalent characterizations. For example, by results of Solovay~\\cite{1975} and of Calude, Hertling, Khoussainov and Wang~\\cite{Calude-Hertling-Khoussainov-Wang}, the Martin-Löf random left-c.e.\\ reals are exactly the halting probabilities of universal Turing machines. Furthermore, Kučera and Slaman~\\cite{Kucera-Slaman-2001} demonstrated that, within the left-c.e.\\ reals, the Martin-Löf random ones form a highest degree of Solovay reducibility, i.e., a left-c.e.\\ real~$\\beta$ is Martin-Löf random if and only if every left-c.e.\\ real~$\\alpha$ is reducible to~$\\beta$. In fact, they showed that the latter holds via arbitrary left-c.e.\\ approximations of~$\\alpha$ and~$\\beta$. As a consequence, given any Martin-Löf random left-c.e.\\ reals~$\\alpha$ and~$\\beta$, they are mutually Solovay reducible to each other via arbitrary left-c.e.\\ approximations~$a_0, a_1, \\ldots$ and~$b_0, b_1, \\ldots$ of~$\\alpha$ and~$\\beta$, respectively, hence, there are reals $c>0$ and $d$ such that, for all~$n$, it holds that\r\n\\begin{equation}\\label{eq:abstract-solovay-constant}\r\nc<\\frac{\\alpha - a_n}{\\beta - b_n}0$ via any left-c.e.\\ approximation of the real. Also speedability is a degree property, i.e., in a Solovay degree, either every or no real is speedable. Furthermore, Martin-Löf random left-c.e.\\ reals are never speedable, while all nonhigh left-c.e.\\ reals are speedable. For speedability defined in terms of monotone Solovay reducibility, some of these results extend to all reals, in particular, robustness with respect to the choice of nonzero~$\\rho$ and the nonspeedability of Martin-Löf random reals. Being Martin-Löf random is not equivalent to being nonspeedable, neither for all reals nor when restricting attention to the left-c.e.\\ reals. The former result is shown below by constructing a right-c.e.\\ counterexample, i.e., a right-c.e.\\ real that is neither Martin-Löf random nor speedable. The latter, more interesting and more difficult result is due to Hölzl and Janicki~\\cite{Hoelzl-Janicki-2023}, who constructed a left-c.e.\\ counterexample. \r\n\r\nThird, the theorem of Barmpalias and Lewis-Pye allows an equivalent reformulation in terms of monotone Solovay reducibility, which can be extended to all reals. This extension is one of the main results of this thesis. A corresponding reformulation in terms of Solovay reducibility is false in general and is actually false\r\nfor all left-c.e.\\ reals."^^ . "2024" . . . . . . . "Ivan"^^ . "Titov"^^ . "Ivan Titov"^^ . . . . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (PDF)"^^ . . . "Ivan-Titov-Dissertation.pdf"^^ . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (Other)"^^ . . . . . . "indexcodes.txt"^^ . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (Other)"^^ . . . . . . "lightbox.jpg"^^ . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (Other)"^^ . . . . . . "preview.jpg"^^ . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (Other)"^^ . . . . . . "medium.jpg"^^ . . . "Solovay Reducibility and Speedability Outside of left-c.e. Reals (Other)"^^ . . . . . . "small.jpg"^^ . . "HTML Summary of #34250 \n\nSolovay Reducibility and Speedability Outside of left-c.e. Reals\n\n" . "text/html" . . . "004 Informatik"@de . "004 Data processing Computer science"@en . . . "510 Mathematik"@de . "510 Mathematics"@en . .