<p>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.</p>

CC BY-SA 3.0
2013-02-25T10:12:54.303Z
Oh, shame on me, this is obvious. Thank you.
Alex
CC BY-SA 3.0
2013-02-25T09:27:58.557Z
2013-02-25T09:27:58.557Z
adrianN
<p>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?</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-02-25T20:37:15.577Z
Voting to close.  This is not a **research-level** question in theoretical computer science; please see the [faq] for more information.
Jeffε
<compressed-sensing>
Proof of non-existence of the universal archiver?
Alex
# Proof of non-existence of the universal archiver?

(Asked by: username_0 on 2013-02-25)

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.

**Tags:** compressed-sensing
> **Comments:**
> **username_1**: Voting to close.  This is not a **research-level** question in theoretical computer science; please see the [faq] for more information.  

---

## 1 answers

### Answer by username_2 on 2013-02-25. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: Oh, shame on me, this is obvious. Thank you.  

---

