"Kolmogorov complexity with time"

111 Views Asked by At

Kolmogorov complexity of object is minimal length of program that print this object.

1)Kolmogorov complexity is not a computable function.

2)If there is little program that print object for billion years we say that Kolmogorov complexity of object is little yet. I think it is strange.

We can define "Kolmogorov complexity with time" of $x$ as min of $\{L_PT_P\}$, where $P$ is program that print $x$, $L_P$ - its length, $T_P$ - is time of its work.

So its definition solve the first and seconds problem. Is there resulats about "Kolmogorov complexity with time"?

1

There are 1 best solutions below

0
On

There's a survey paper here of some "resource bounded" variants of Kolmogorov complexity and their relation to complexity theory. It doesn't have your exact definition, but Levin's and Allender's (definition 2.5 and 2.6 respectively) are pretty close.