-3
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Oh, shame on me, this is obvious. Thank you. $\endgroup$ – Alex Feb 25 '13 at 10:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.