next up previous
Next: Generalized Kolmogorov Complexity for Up: HIERARCHIES OF GENERALIZED KOLMOGOROV Previous: Weak Decidability and Convergence


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
\begin{displaymath}
K(x) = \min_{p}\{l(p) : U(p)=x \}.
\end{displaymath} (4)

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



Subsections

Juergen Schmidhuber 2003-02-13