Publication – Page 6 – Kenshi Miyabe

Abstract
We correct Miyabe’s proof of van Lambalgen’s Theorem for truth-table Schnorr randomness (which we will call uniformly rela- tive Schnorr randomness). An immediate corollary is one direction of van Lambalgen’s theorem for Schnorr randomness. It has been claimed in the literature that this corollary (and the analogous result for com- putable randomness) is a “straightforward modification of the proof of van Lambalgen’s Theorem.” This is not so, and we point out why. We also point out an error in Miyabe’s proof of van Lambalgen’s Theorem for truth-table reducible randomness (which we will call uniformly rel- ative computable randomness). While we do not fix the error, we do prove a weaker version of van Lambalgen’s Theorem where each half is computably random uniformly relative to the other.

Category: Publication

Computation with advice of degree of randomness

Analytical approach to algorithmic randomness

Schnorr and Kurtz randomness versions of Merkle’s criterion

Van Lambalgen’s Theorem for uniformly relative Schnorr and computable randomness

Computability of conditional probability