Here is the URL for retreat and ARA 2014 Japan

Please note it starts on Sept 1 morning, so be there on August 31 if at all possible.

Kenshi and André

Leave a reply

Here is the URL for retreat and ARA 2014 Japan

Please note it starts on Sept 1 morning, so be there on August 31 if at all possible.

Kenshi and André

André has posted the Logic Blogs from previous years on ArXiv:

First of all: thanks to Rupert for putting up this blog. It looks great! My first post will be a question which I stumbled upon while working on effective Brownian motion with Kelty Allen:

Let $X$ be an ML random real and $Y$ some real. Is there always a sequence $R$ of rationals converging to $Y$ such that $X$ is random relative to $R$?

Of course the only interesting case is when $X$ is *not* ML-random relative to $Y$. Note that the answer is no if we further ask $R$ to be nondecreasing (take $X=\Omega$ and $Y=1-\Omega$: any nondecreasing sequence converging to $1-\Omega$ computes $1-\Omega$ so it derandomizes $X$)

There finally is a Wikipedia article on K-triviality

It was originally written by me and my summer student Jing Zhang (NUS)

Lots of red links there to be filled.

Andre

For the meeting schedule and for slides click here.

For a list of open problems discussed at the workshop, click here.

For a report from the preceeding retreat at Intundla Lodge click here.

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

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

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?

*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]*