1
$\begingroup$

I've had several Computer Science courses and, from what I recall, I've never been given a rigorous definition of suitable encoding. Definitions always tend to use effective method or some synonym to define a suitable encoding, even though the reason we are defining suitable encodings is to formalize what an effective method is. I've recently discussed it with some of my classmates and we found a few necessary condition but could not find sufficient ones.


Let $X$ be set of things and $\Sigma$ an alphabet. An encoding is an injective function $e:X\to \Sigma^*$. The associated code is $e(X):=\{e(x) : x \in X\}$. Given a subset $P\subseteq X$, we say that it is $e$-decidable is $e(P)$ is decidable (as a subset of $e(X)$).

Given two encodings $e$ and $e'$, we call translation from $e$ to $e'$ the unique function $f_{e\to e'}:e(X)\to e'(X)$ so that for all $x\in X, f_{e\to e'}(e(x))=e'(x)$.

If $f_{e\to e'}$ is computable, then any $e'$-decidable problem is also $e$-decidable. We will therefore say that $e'$ is a better encoding than $e$ and write $e\rightsquigarrow e'$. Intuitively, we want the encoding to contains as little information as possible (so to minimize the set of decidable problems) but still have enough information to know which element we're talking about (hence the injectivity of $e$).

For example, for $X=\{(M,w):\text{ Turing machine and } w \text{ word}\}$, if we call $e'$ one standard encoding and $e(M,w):=e'(M,w)b$ where $b$ is $1$ if $M$ halts on $w$ and $0$ otherwise. The halting problem is $e$-decidable but not $e'$-decidable. The function $f_{e\to e'}(ub):=u$ is computable so $e'$ is a better encoding than $e$.

We say that two encodings are equivalent, and write $e\sim e'$ if $e\rightsquigarrow e'$ and $e'\rightsquigarrow e$. Given a suitable encoding $e$, the suitable encodings are exactly those equivalent to $e$. But I feel like there should be some way to define suitable encodings without needing to give a specific one.

Let $e'$ be a an encoding so that for any encoding $e$, if $e\rightsquigarrow e'$, then $e'\rightsquigarrow e$ (and $e\sim e'$). We will call $e'$ a minimal encoding. An minimal encoding is an encoding better than any encoding it is comparable to. If $e\sim e'$, $e'$ is minimal iff $e$ is.

And encoding $e$ is called decidable if $e(X)$ is. If $e\sim e'$, $e'$ is decidable iff $e$ is.


A suitable encoding should probably be minimal and decidable but that doesn't seem to be enough to characterize them. Intuitively, there seems to be several equivalence classes of minimal decidable encodings, but there is only one that really represents what we want to call suitable encodings.

A solution could be to add "If an encoding $e$ is suitable, then for any $e'$, any non $e'$-decidable problem is not $e$-decidable.". But I'm pretty sure one can build a minimal decidable encoding for integers so that beeing even is undecidable. Let $(M_n)_n$ be an enumeration of Turing machines. We can extract two subenumerations $(M_{\varphi(n)})_n$ (resp. $(M_{\psi(n)})_n$) of machines that halt (resp. do not halt) on all inputs. Then we define $e(2n)=e'(\varphi(n))$ and $e(2n+1)=e'(\psi(n))$ where $e'$ is some suitable encoding.

Another idea is to say that the suitable encodings must somehow be more robust and so its equivalence class must be bigger. But both will be countable...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.