Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by JɛffE, Andrej Bauer, Lev Reyzin, Dave Clarke Mar 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.

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

1 Answer 1

up vote 2 down vote accepted

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.

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

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