Author Archives: Jason Rute

About Jason Rute

I am mathematical logician and post doc in the Penn State mathematics department. I specialize in algorithmic randomness, reverse mathematics, effective mathematics, and quantitative analysis.

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.

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.)