Growth and irreducibility in path-incompressible trees
Abstract
We study effective randomness-preserving transformations of path-incompressible trees. Some path-incompressible trees with infinitely many paths do not compute perfect path-random trees with computable oracle-use. Sparse perfect path-incompressible trees can be effectively densified, almost surely. We characterize the branching density of path-random trees.
Content Overview
A string is a finite binary sequence, and a real is an infinite one. A tree is a set of finite strings closed under prefix. A real $x$ is a path of a tree $T$ if $\sigma\prec x$ implies $\sigma\in T$. A string branches in a tree $T$ if it has at least $2$ incomparable extensions in $T$.
Let $K(\cdot)$ denote the prefix-free Komogorov complexity. The deficiency of a string $\sigma$ is $|\sigma|-K(\sigma)$. The deficiency of a set of strings is the supremum of the deficiencies of its members.
A tree is path-incompressible if it has finite deficiency. A tree is proper if it has infinitely many paths. A tree $T$ is perfect if each string in $T$ branches in $T$.
Theorem. There is a path-incompressible proper tree that does not wtt-compute any path-incompressible perfect tree.
Open problem
Is there a path-incompressible proper tree that does not compute any path-incompressible perfect tree?
Links and resources
