pith. sign in

arxiv: 1408.1967 · v1 · pith:B5TXINOSnew · submitted 2014-08-08 · 🧮 math.LO

A strong law of computationally weak subsets

classification 🧮 math.LO
keywords mathcalinfiniterandomsubsetalmostcomputablecomputationallycomputes
0
0 comments X
read the original abstract

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event $\mathcal A$ such that if $X\in\mathcal A$ then $X$ has an infinite subset $Y$ such that no element of $\mathcal A$ is Turing computable from $Y$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.