# Dependence of decidability on the encoding of Turing machines

Let $$f : \{0, 1\}^* \to \{0, 1\}^*$$ be a computable function. Given any encoding $$\left$$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of strings over $$\{0, 1\}^*$$), consider the following language:

$$L_f = \{\left \mid M \mathrm{\ accepts\ } f(\left)\}$$

Question: Does there exist a function $$f$$ for which the decidability/recognizability of this language depends upon the particular encoding used?

Claim: for any function $$f:\{0,1\}^*\to\{0,1\}^*$$ (not necessarily computable) and any admissible (see comments below) encoding, the language $$L_f = \{\left \mid M \mathrm{\ accepts\ } f(\left)\}$$ is not decidable. Proof. Suppose, for a contradiction, that $$L_f$$ is decidable -- say, by a TM $$M_f$$. Now we construct the following TM $$M'$$. First, $$M'$$ computes its encoding $$\left$$ -- which it can, using the Recursion Theorem. Then, $$M'$$ runs $$M_f$$ with input $$\left$$, which tells it whether or not $$M'$$ is supposed to accept $$f(\left)$$. If the answer is YES, then $$M'$$ rejects every input, otherwise, $$M'$$ accepts every input. In any case, the behavior of $$M'$$ contradicts the prescription furnished by $$M_f$$ -- a contradiction.

Update. Of course, if $$f$$ is computable, then $$L_f$$ is in RE (i.e., is Turing-recognizable) --- trivially so.

• Thanks, this is interesting. Didn't know the Recursion theorem before. – RandomStudent Sep 21 '20 at 8:24
• This does not work for arbitrary encodings, but only for those that satisfy the recursion theorem. – Emil Jeřábek Sep 21 '20 at 12:56
• What are the conditions for an encoding to satisfy the recursion theorem? – Aryeh Sep 21 '20 at 12:58
• Admissible numberings of Turing machines satisfy it, but in general, you are not going to get necessary and sufficient conditions simpler than “those that satisfy the recursion theorem”. – Emil Jeřábek Sep 21 '20 at 13:52
• I modified my answer, but I'd like to get to the bottom of this sometime. Sipser certainly glosses over it, defining an encoding as a mapping from an object (algorithm, TM) to a string. Everything seems to work; where is he cheating? – Aryeh Sep 21 '20 at 14:05

For a given computable $$f$$, the decidability of $$L_f$$ is independent of the encoding of Turing machines if and only $$f$$ is eventually injective (i.e., there exists a finite $$X\subseteq\def\N{\mathbb N}\N$$ such that $$f\restriction(\N\smallsetminus X)$$ is injective, or equivalently, $$\{\def\<#1>{\langle#1\rangle}\:n\ne m,f(n)=f(m)\}$$ is finite).

1. If $$f$$ is computable and eventually injective, then $$L_f$$ is undecidable for any encoding.

Assume for contradiction that $$L_f$$ is decidable. Then $$\{m\in\N:\exists n\in\N\:(f(n)=m\land n\notin L_f)\}$$ is r.e., hence it is accepted by infinitely many Turing machines; in particular, using the assumption, it is accepted by a TM $$M$$ such that $$f(n)\ne f(\)$$ for all $$n\ne\$$. Then $$\\in L_f\iff M\text{ accepts }f(\)\iff\\notin L_f,$$ a contradiction.

1. If $$f$$ is not eventually injective, then the decidability of $$L_f$$ depends on the encoding.

As shown in Aryeh’s answer, $$L_f$$ is undecidable under the standard encoding, hence it suffices to exhibit an encoding that makes $$L_f$$ is decidable. Let $$\{M_m:m\in\N\}$$ be any enumeration of TMs, and define $$X\subseteq\N$$ by $$n\in X\iff|\{m We define a new enumeration $$\{M'_n:n\in\N\}$$ by $$M'_n=M_{m(n)}$$, where $$m(n)$$ is defined by induction on $$n$$: $$m(n)=\begin{cases} \min\bigl\{m\in\N\smallsetminus\{m(i):i To see that $$\{M'_n:n\in\N\}$$ indeed enumerates all TMs, assume for contradiction that $$m$$ is least such that $$m\ne m(n)$$ for all $$n\in\N$$. Since $$f$$ is not eventually injective, there are $$n such that $$f(n)=f(n')$$ and $$\{0,\dots,m-1\}\subseteq\{m(i):i. We may assume $$n'>n$$ is smallest such that $$f(n')=f(n)$$, which implies $$n\in X\iff n'\notin X.$$ Thus, either $$n''=n$$ or $$n''=n'$$ satisfies $$M_m\text{ accepts }f(n'')\iff n''\in X,$$ which implies $$m(n'')=m$$ by the definition of $$m(n'')$$, a contradiction.

Thus, we may define an encoding of TM by $$\=n$$, and then it follows from the definition that $$L_f=X,$$ which is decidable.

The answer above assumes that an encoding of TM has to be injective; this is not specified in the OP, but I suppose this is just an omission, as I fail to see how something that assigns the same code to two different TM can be considered an “encoding” of TM.

Anyway, if we allow non-injective encodings, the answer is that the decidability of $$L_f$$ depends on the encoding for every $$f$$: it is undecidable under the standard encoding by Aryeh’s answer, while it is trivially decidable (because finite) for the constant encoding $$\=0$$.

• Nice! Thanks for the illuminating answer! =) – user21820 Sep 28 '20 at 17:06