# Proof of non-existence of the universal archiver? [closed]

Does anybody knows a proof that no algorithm $A$ exists that can reversibly transform every possible finite sequence $S$ to the sequence $C$ of smaller size?

Here I assume $S$ and $C$ to be a finite bit sequences (or more generally some finite sequences of elements from certain finite set), algorithm should be executed in the finite time for each sequence S and use finite memory. The same constraints applies for the reverse algorithm $A^{-1}$ - it should consume finite memory and "unpack" certan sequence in the finite time.

I guess such a proof would be trivial one, but I forgot how the formal proof is done.

-

## closed as off topic by Jeffε, Andrej Bauer, Lev Reyzin♦, Dave ClarkeMar 22 '13 at 22:34

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Voting to close. This is not a research-level question in theoretical computer science; please see the faq for more information. – Jeffε Feb 25 '13 at 20:37

Assume there is a program that maps every sequence of $n$ bits to a sequence of $n-1$ bits. There are $2^n$ sequences with $n$ bits, but only $2^{n-1}$ sequences with $n-1$ bits. Hence there are two sequences $S,S'$ that get mapped to the same sequence $C$. Therefore there can be no algorithm that reverses the transformation.

-
Oh, shame on me, this is obvious. Thank you. – Alex Feb 25 '13 at 10:12