Kolmogorov Complexity vs Running Time (Edited)

Question

Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$.

I believe that the time it takes for the universal Turing machine to evaluate $A$ on input $i$ should be $\Theta(n)$. I'm not familiar with Kolmogorov complexity, and I wanted to ask if the following intuition is correct

1. An upper bound on the running time of $A$ is $O(n)$, since the description of $A$ can just list the whole string $s$ and return $s_i$ on input $i$. The universal Turing machine on inputs $(A,i)$ simply reads the description of $A$ (Which is $O(n)$ in length) and outputs the $i^{th}$ coordinate (which takes time $\log n$)

2. A lower bound on the running time of $A$ can be proved as follows.

   a. The description length of $A$ must be at least $n - log n - c$ for a constant $c > 0$. This is because the program $B$: "Run $A$ on every input from $1$ to $n$" has description length $DL(B) = DL(A) + log(n) + c$ and generates the string $s$. Thus $DL(B) \geq n$ and $DL(A) \geq n- \log(n) - c$.

   b. The universal Turing machine $U$ on input $(A,i)$ needs to read both $A$ and $i$, which requires at least $DL(A) + \log n \geq n-c$ operations.

Is this intuition correct? Or am I missing something big about Kolmogorov complexity?

Answer 1

It really depends on your computation model. Suppose for example a model which allows random "seek" instructions, say the RAM machine. The algorithm $A$ can just include a description of the string, and on input $i$ you output the $i$th bit of the string. Conceivably, a universal Turing machine (running on a RAM machine) can execute this algorithm in time $O(\log n)$, especially if we engineer it to specifically handle algorithms of this type.

Any proof that a universal Turing machine (running on an actual Turing machine) requires time $\Theta(n)$ thus needs to appeal specifically to the Turing machine model. In particular, you claim that the universal Turing machine $U$ must read all of $A$ and $i$. But in fact, for any given string $s$ we can construct a universal Turing machine whose programs come in two types: (1) output $s$; (2) everything else. Such a Turing machine can "simulate" $A$ in time $O(\log n)$. The correct claim you should try to prove thus needs to accommodate finitely many exceptions, unless you are fixing a universal Turing machine. (On second thought, it's not clear whether you can pull it off while keeping the string random. Indeed, it seems you won't be able to recognize the program $A$ without reading all of it, which would take time $n$ if the string is Kolmogorov random.)

Even if we fix a universal Turing machine, it's not clear that $A$ necessarily takes time $O(n)$. We can arrange for $A$ to first output $n!$ many zeroes, then erase them and proceed as in your algorithm. Perhaps you meant $A$ to be the one with the lowest time complexity? (say the one minimizing the maximal execution time over all indices)