Generalized Kolmogorov Complexities for generalized Turing machines (Schmidhuber, 2000)

• TM U: K(x)=min {l(p): U(p)=x, p halts}

• U(p)? x: program p converges to x

• MTM U: KM(x)=min {l(p): U(p) ? x}

• EOM U: KE(x)=min {l(p): U(p) ? x}

• GTM U: KG(x)=min {l(p): U(p) ? x}

• GTM U: KmG(x)=min {l(p): U(p) ? xz}

• K and KE describable, KG not (Theorem 3.1)

Previous slide

Next slide

Back to first slide

View graphic version