Encoding of data

Remarks

Every encoding has a decoding, since $e$ is injective; in computability one also asks that $e$ and a decoding be computable. Example: the binary numeral without leading zeros, with $0$ written as $0$, is an encoding of $\N$ over $\set{0, 1}$. It is injective, since a numeral without leading zeros determines its value and the value determines the numeral. Non-example: the map $\N \to \set{0,1}^*$ that sends $n$ to its last binary digit is not an encoding, since $1$ and $3$ both get the string $1$. Codes of pairs are often built by concatenation with a separator, for example $\langle a, b \rangle = \langle a \rangle \# \langle b \rangle$ over $\Sigma \cup \set{\#}$. A Gödel numbering is an encoding into $\N$ instead of $\Sigma^*$, and binary numerals turn one into the other.