next up previous
Next: Hamming fitness is Binomial Up: Reversible Programs are Normal Previous: Background - Irreversible Fitness

Proof for reversible computing

For simplicity ignore constants and garbage bits, so all $N$ wires can take any of $2^{N}$ values.

The computer program performs a $2^{N} \rightarrow 2^{N}$ mapping. Consider the mapping as a truth table with $2^{N}$ rows.

There are up to $2^{N\times 2^{N}}$ possible tables.

To be reversible, from the output we can infer the input.

Each row in the truth table must be unique. I.e. the truth table contains a permutation of $2^{N}$ numbers.

There are only $2^{N}!$ truth tables (only $2^{N}!$ reversible functions). Only $e^{-2^{N}}$ functions are reversible.

Each reversible function can be represented by a number $1 \ldots 2^{N}!$

$N=6$ example
look up table
$N\times 2^{N}=384$ bits $2^{384}=3.9\ 10^{115}$
$2^{N}!= 6.3\ 10^{87}$


next up previous
Next: Hamming fitness is Binomial Up: Reversible Programs are Normal Previous: Background - Irreversible Fitness
Bill LANGDON 2003-05-26