Complexity of Constructive Descriptions next up previous contents
Next: Generalized Kolmogorov Complexity for Up: No Title Previous: Weak Decidability and Convergence

   
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

 \begin{displaymath}K(x) = \min_{p}\{l(p) : U(p)=x \}.
\end{displaymath} (6)

Let us now extend this to nonhalting GTMs.



 

Juergen Schmidhuber
2001-01-09


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