Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$.

I recall the definition of the algorithmic complexity of a string relative to a partial recursive function $F$: $C_{F}\left(x\right)=\min\left\{ \left|y\right|\in B^{<\omega}\mid F\left(y\right)=x\right\} $.

In algorithmic complexity theory, we often use what is called an optimal decompressor. An optimal decompressor is a partial recursive function $U$ from $B^{<\omega}$ to $B^{<\omega}$ which verifies « For any partial recursive function F, $C_{U}\left(F\left(x\right)\right)\leq\left|x\right|+O\left(1\right)$ ».

Now, this is purely an information-related concept, and it tells us nothing about whether $U$ can be seen as a usable « programming language ». We can define a stronger concept: an effectively optimal decompressor is a partial recursive function $U$ such as we can find a recursive and length-preserving translation from any other partial recursive function into $U$. Formally, $U$ is a partial function such that for any partial recursive function $F$, there exists a total recursive function $h$ such as $U\left(h\left(x\right)\right)=F\left(x\right)$ for all $x$, and such that $\left|h\left(x\right)\right|\leq\left|x\right|+O\left(1\right)$.

It is easy to show that those two definitions are not equivalent. But one of my colleagues asked the question: what if, in the definition of effective optimality, we only ask that $h$ verifies « If $F(x)$ is defined, then $U(h(x))=F(x)$ »? In other terms, what if we allow $h$ to output a program which halts when the input is a program which doesn't halt? Note that $h$ still has to be a total recursive function. It gives a definition which is stronger than the first definition (non-effective optimality), but I can't prove that it is equivalent, or strictly weaker, than the second definition.

It sounds like a question which is too simple not to have an easy answer, but I've been stuck on it for the last few days. If someone has an idea, I'm all ears =)

Thank you in advance!

  • $\begingroup$ In case it's not clear: in the definition of effective optimality, « $U(h(x))=F(x)$ for all $x$ » implicitely implies « if F(x) is not defined, then U(h(x)) is not defined either ». $\endgroup$
    – Ted
    Jun 24, 2014 at 5:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.