Effective binary encodings and total decoders

Let $\mathbb{B}:=\{0,1\}$. A binary encoding of a set $X$ is an injective function $e:X\to {\mathbb{B}}^{\ast }$ (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, Injection, surjection, bijection).

Fix a symbol $\mathtt{m}\mathtt{a}\mathtt{l}$ not belonging to $X$. A total decoder for $e$ is a function $d:{\mathbb{B}}^{\ast }\to X\cup \{\mathtt{m}\mathtt{a}\mathtt{l}\}$ such that $d(e(x))=x(x\in X),d(w)=\mathtt{m}\mathtt{a}\mathtt{l}(w\mathrm{\notin }e[X])\mathrm{.}$ Thus $\mathtt{m}\mathtt{a}\mathtt{l}$ is exactly the output on malformed codes, and the decoder is defined on every binary word, not only on words in the image of $e$.

The encoding $e$ is effective when such a total decoder is specified.

The encoding is prefix-free when no codeword is a proper prefix of another: there do not exist distinct $x,y\in X$ and a nonempty binary word $u$ with $e(y)=e(x)u$.

• Effectiveness here means injective plus explicitly decodable with a fixed malformed-code output. It does not yet formalize computation by Turing machines.

• Prefix-freeness is an additional property, not part of the definition of an effective encoding.