Author Archives: Rupert Hölzl

About Rupert Hölzl

Research Fellow at the National University of Singapore.

CCR 2014: Open questions

For a slightly more detailed discussion of the following questions, see the PDF version of the Logic Blog.

Computable randomness

Let $\mathrm{CR}$ denote the class of computably random sets.

Question. (van Lambalgen’s theorem for $\mathrm{CR}$) Let $X$ be computably random, and let $Y$ be computably random relative to $X$. Is $X \oplus Y$ computably random?

Question. (Joseph Miller) Let $X$ be computably random. Is there an incomputable oracle $A$ such that $X$ is computably random relative to $A$?

 

Let $\textrm{High}(\textrm{CR}, \textrm{MLR})$ denote the class of oracles $A$ such that $\textrm{CR}^A \subseteq \textrm{MLR}$.

Question. (Joseph Miller) Is every set in  $\mathrm{High}(\mathrm{CR}, \mathrm{MLR})$ PA-complete?

 

We write $A \le_{\mathrm{CR}} B$ if $\mathrm{CR}^B \subseteq \mathrm{CR}^A$.

Question.  (Nies) Is $\le_{\mathrm{CR}}$ equivalent to $\le_\mathrm{T}$?

 

Martin-Löf randomness

Let $A \triangle B$ denote the symmetric difference of sets $A$, $B$.

Definition. (Kihara) We say that $A$ is ML-additive if $Z \in \mathrm{MLR}$ implies $Z \triangle A\in \mathrm{MLR}$ for each $Z$.

Clearly every low for ML-random is ML-additive.

Question. Is every ML-additive oracle low for ML-randomness?

 

Definition. (Yu) We say $A$ is absolutely low for $R$ if for all $Y$,

$R \in \mathrm{MLR}^Y \rightarrow R\in\mathrm{MLR}^{Y\oplus A}.$

Fact. (Stephan and Yu) Let  $A$ be $K$-trivial. Then $A$ is absolutely low for $\Omega$.

Question. (Yu) Is every set that is absolutely low for $\Omega$ $K$-trivial?

Definition. (Merkle) We say an oracle $A$ is super-absolutely low for $\Omega$  if for each oracle  $Y$ which is low for $\Omega$,

$\forall n(K^Y(n)=K^{A\oplus Y}(n)+O(1)).$

Note that every such set  is  absolutely low for $\Omega$ by definition. In fact it  must be  low for $K$, by letting $Y= \emptyset$. We ask the converse.

Question. (Merkle) Is every low for $K$ set super-absolutely low for $\Omega$?

Brattka, Gherardi, Hölzl: Probabilistic Computability and Choice

Available on arXiv.

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak König’s Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. Continue reading

Open questions from ARA

A list of open problems as discussed during the 2013 La Mothe retreat and during ARA 2013 in Nancy.

Computable randomness

If \(X\) is computably random and \(Y\) is \(X\)-computably random, is \(X \oplus Y\) computably random?

[J. Miller] Is there a computably random \(X\) such that for every non-computable \(Y\), \(X\) is not \(Y\)-computably random?

Randomness and Turing degrees

Continue reading

$K^X \ge_T X$

Written by Turetsky. Proved by Miller and Turetsky, and then vastly simplified by Bienvenu.

Proposition. For any real $X$, $K^X \ge_T X$.

Proof. $X$ is $X$-trivial. That is, $K^X(X\!\!\upharpoonright_n) \le K^X(n) + c$. Note that $K^X$ can compute the tree $\{\sigma \in 2^{<\omega} : K^X(\sigma) \le K^X(|\sigma|) + c\}$. This tree has finitely many infinite paths, and $X$ is one of them. As an isolated path, $K^X$ can compute $X$. [Source: The 2013 Logic Blog, page 31]