Complexity of Constructive Descriptions

The remaining sections of this paper contain its main contributions, embedded in the context of earlier work.

Traditionally, the Kolmogorov complexity [25,40,13] or algorithmic complexity or algorithmic information of $x in B^*$ is the length of the shortest halting program computing $x$:

Definition 3.1 (Kolmogorov Complexity $K$)   Fix a universal MTM or EOM or GTM U with halt instruction, and define

$$K(x) = \min_{p}\{l(p) : U(p)=x \}.$$ (4)

We will now extend this in novel ways to nonhalting EOMs and GTMs.