Total conditional complexity

Question

By $C(|)$ denote conditional complexity.

By $CT(|)$ denote total conditional complexity.

For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$ but $CT(x|y) \ge n $.

It is proved there: http://arxiv.org/pdf/1204.0198.pdf pages 5-6.

It is easy to see that $x$ have the same information as $y$ (Let us denote it $ x \sim y$)

What is the information?

By $T_n$ denote number of total programs with length $< n$.( $T_n \sim N_k$ - number of integers with complexity $\le n$. $N_k \sim \Omega_n$ - the first $n$ bits Chaitin's number.)

Let $x=x_n$ and $y=y_n$ where $x_n$ and $y_n$ are the same as in article. Then $x \sim T_n$: we can play this computable game until Alice add $x_n$ - so we find $T_n$.

Question: let $x$ and $y$ have lengths $n$ , $C(x|y) = O(1)$ and $CT(x|y) \ge n $.

Is it true that $x \sim T_n$ necessarily?

Answer 1

Yes it is true.

Let $x$ and $y$ be strings with lengths $n$ and $C(x|y) = D =const$, $CT(x|y) \ge n$.

There is program $p$ with length $D$ such that $p(x) = y$ (we assume that we fixed some Turing machine).

Denote by $t$ - time (number of elementary operations) that need to compute $f(x)$ ($C(t|x) = O(1)$).

Let us show that $t$ is large.

Denote by $M$ all total programs with length $ \le m$, $m \le n$.

Denote by $t_m$ maximal time of working program from $M$ with input from $\{0,1\}^n$.

Let us show that $t > t_m$ for $m = n - O(\log n)$. Before proving this statement let us explain why it proves that need. By $x$ we can get $t$. By $t$ we can get $|M|$ (or $T_m$ or $\Omega_m$) - for it need to run all programs with length $m$ on all inputs with lengths $n$ and wait time $t$.

Assume the converse. Then there is program $p_1$ with length $\le m + O(\log n)$ that write number $t_1$ that large then $t$ ($p_1$ is without input). So there is program with length $\le m + O(\log n)$ such that for any $a \in \{0,1\}^n$ it write list $(a_1,...a_k)$ such that $C(a_i|a) \le D$ and corresponding program work $\le t_1$. In list that corresponds to $x$ there is $y$. Now it is easy to see that there is total program with length $m + O(\log n)$ that correspond $x$ to $y$ (it need to fix some rule for choice some element from list). Hence $m \ge n - O(\log n)$. Hence there is $m = n - O(\log n) $ such that $t > t_m$.