Complexity of Constructive Descriptions

Throughout this paper we focus on TMs with self-delimiting programs [#!Levin:73a!#,#!Levin:74!#,#!Gacs:74!#,#!Chaitin:75!#]. Traditionally, the Kolmogorov complexity [#!Kolmogorov:65!#,#!Solomonoff:64!#,#!Chaitin:69!#] 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 tex2html_wrap_inline$K$)   Fix a universal MTM or EOM or GTM U with halt instruction, and define

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

Let us now extend this to nonhalting GTMs.

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI