Dimensionality and randomness

Abstract

The deficiency of a string is the maximum number of bits it can be compressed. We study sets of strings with finite (bounded) deficiency, which are called incompressible sets. Among them, observation shows that “thin” ones cannot be effectively transformed into “fat” ones unless they are complete. For example, a random real cannot compute an incompressible tree with infinitely many paths unless it is complete. In this talk, we provide several theorems in this form, and quantify what conditions are needed on the fat set to prevent it from being computed from a thin one.

Links and resources

• slide pdf

Relevant contents

• article - Dimensionality and randomness
• article - Growth and irreducibility in path-incompressible trees