  Two objects are independent if they do not affect each other. Independence is
well-understood in classical information theory, but less in algorithmic
information theory. Working in the framework of algorithmic information theory,
the paper proposes two types of independence for arbitrary infinite binary
sequences and studies their properties. Our two proposed notions of
independence have some of the intuitive properties that one naturally expects.
For example, for every sequence $x$, the set of sequences that are independent
(in the weaker of the two senses) with $x$ has measure one. For both notions of
independence we investigate to what extent pairs of independent sequences, can
be effectively constructed via Turing reductions (from one or more input
sequences). In this respect, we prove several impossibility results. For
example, it is shown that there is no effective way of producing from an
arbitrary sequence with positive constructive Hausdorff dimension two sequences
that are independent (even in the weaker type of independence) and have
super-logarithmic complexity. Finally, a few conjectures and open questions are
discussed.
