Category Archives: Computability theory

On the computability of compact groups

Andre Nies and I recently uploaded an article to the logic blog about the computability of compact groups. This was based on some discussion in Oaxaca, Mexico.

In particular, we show when the Haar measure of a compact group is computable, and when a group is a computable profinite group.

The article is titled “On the computability of compact groups”. We thank Alexander Melnikov for a fruitful discussion over email.

Connections between randomness and profinite groups

The current Logic Blog, Section 15 or so  contains new connections of randomness with algebra. Given a computable profinite group  the Haar measure is computable, so all the usual notions work. I’ve added one example where the effective form of an a.e. theorem needs only  Kurtz randomness. For other examples not even arithmetical randomness looks sufficient at present.

Indexing the LB

This year’s will be the 6th instalment of the Logic Blog (which started in 2010). There is so much stuff on it by now that it becomes hard to find particular things. I’ve thought of putting it all into one file and give it an index. Any offers of help for this?

Andre

K-trivial, K-low and ML-low: a tutorial

This year Laurent Bienvenu (visiting Moscow) taught a course on Kolmogorov complexity and randomness; at the end he tried to present the equivalence between these three notion in a less formal and more easy-to-read way. After several discussions, we tried to write down an exposition of the proof, now added to pdf-logic-blog. This is essentially the original proof, but we tried to present it in a more structured way; the technical difference is mostly in explicit game interpretation (the result is a corollary of an existence of a winning strategy in a combinatorial game) and n the different `flow of control’: now the strategy is described as a family of parallel threads (each of them recursively creates other threads, etc.) that are waked up and put into sleep depending on the changes in the opponent’s path.

Hope this could help future readers (and lecturers) – and thanks in advance for comments…

gentle introduction to triviality

No-randomness-from-nothing for computable randomness

I recently added the short article “No-randomness-from-nothing for computable randomness” to the 2014 PDF Logic Blog.

There are two important properties that one would like a notion of algorithmic randomness to have.  The first is called randomness preservation.  It says that if $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is a computable measure-preserving map and $X \in \{0,1\}^\mathbb{N}$ is random, then so is $T(X)$.  While this property holds for most randomness notions—Kurtz randomness, Schnorr randomness, Martin-Löf randomness, weak $n$-randomness, difference randomness, Demuth randomness, Oberwolfach randomness, and $n$-randomness—it fails for computable randomness. (Nonetheless, I have work in preparation—extending previous work—showing that randomness preservation for computable randomness holds for all “naturally occurring” computable measure-preserving maps, but this is not the purpose of this article.)

The purpose of this article to show that the dual property, no-randomness-from-nothing, holds for computable randomness.

Theorem (No-randomness-from-nothing for computable randomness).  Assume $\mu$ is a computable measure and $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is an a.e. computable measure-preserving map.  If $Y \in \{0,1\}^\mathbb{N}$ is computably random, then there is some $X \in \{0,1\}^\mathbb{N}$ such that $T(X)=Y$.

(The proof can be found in the PDF Logic Blog.)

It is previously known that no-randomness-from-nothing holds for Martin-Löf randomness, weak $n$-randomness ($n\geq2$), and $n$-randomness.  This theorem answers a question of Bienvenu and Porter, who asked if it is true for Schnorr and computable randomness. The Schnorr randomness case still remains open.

Open question.  Does no-randomness-from-nothing hold for Schnorr randomness?

(Although, once again, I have work in preparation showing that no-randomness-from-nothing for Schnorr randomness holds for all “naturally occurring” computable measure-preserving maps.)

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$?

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