<p>Claim: for <em>any</em> function <span class="math-container">$f:\{0,1\}^*\to\{0,1\}^*$</span> (not necessarily computable) and any admissible (see comments below) encoding, the language
<span class="math-container">$$ L_f = \{\left&lt;M\right&gt; \mid M \mathrm{\ accepts\ } f(\left&lt;M\right&gt;)\} $$</span>
is not decidable.
Proof. Suppose, for a contradiction, that <span class="math-container">$L_f$</span> is decidable -- say, by a TM <span class="math-container">$M_f$</span>. Now we construct the following TM <span class="math-container">$M'$</span>. First, <span class="math-container">$M'$</span> computes its encoding <span class="math-container">$\left&lt;M'\right&gt;$</span> -- which it can, using the Recursion Theorem. Then, <span class="math-container">$M'$</span> runs <span class="math-container">$M_f$</span> with input <span class="math-container">$\left&lt;M'\right&gt;$</span>, which tells it whether or not <span class="math-container">$M'$</span> is supposed to accept <span class="math-container">$f(\left&lt;M'\right&gt;)$</span>. If the answer is YES, then <span class="math-container">$M'$</span> rejects every input, otherwise, <span class="math-container">$M'$</span> accepts every input. In any case, the behavior of <span class="math-container">$M'$</span> contradicts the prescription furnished by <span class="math-container">$M_f$</span> -- a contradiction.</p>
<p>Update. Of course, if <span class="math-container">$f$</span> is computable, then <span class="math-container">$L_f$</span> is in RE (i.e., is Turing-recognizable) --- trivially so.</p>

CC BY-SA 4.0
2020-09-21T08:24:24.793Z
Thanks, this is interesting. Didn't know the Recursion theorem before.
RandomStudent
CC BY-SA 4.0
2020-09-21T12:56:37.360Z
This does not work for arbitrary encodings, but only for those that satisfy the recursion theorem.
Emil Jeřábek
CC BY-SA 4.0
2020-09-21T12:58:44.220Z
What are the conditions for an encoding to satisfy the recursion theorem?
Aryeh
CC BY-SA 4.0
2020-09-21T13:52:12.970Z
[Admissible numberings](https://en.wikipedia.org/wiki/Admissible_numbering) 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
CC BY-SA 4.0
2020-09-21T14:05:38.403Z
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
CC BY-SA 4.0
2020-09-21T14:07:48.300Z
A minimal property you want an encoding to satisfy is that two non-equivalent objects don't get mapped to the same string.
Aryeh
CC BY-SA 4.0
2020-09-21T14:08:05.670Z
What else can you impose, at that level of abstraction?
Aryeh
CC BY-SA 4.0
2020-09-21T16:49:02.503Z
Well, there are all kinds of things you might impose. E.g., you can impose that various constructions on Turing machines are computable; in particular, the s-m-n theorem (given an encoding of a Turing machine and an input, you can compute an encoding of the corresponding Turing machine where that input is hard-wired). Or, you can impose that there is a universal Turing machine: i.e., $U$ such that $U(\langle M\rangle,x)\simeq M(x)$.
Emil Jeřábek
CC BY-SA 4.0
2020-09-21T17:21:04.403Z
Ah yes—in our course we do precisely the latter. We state it as a theorem and majorly handwave the proof. I guess mischief can occur here if careless.
Aryeh
CC BY-SA 4.0
2020-09-27T18:29:03.547Z
@EmilJeřábek: Can you actually prove that there is some bad encoding that makes this particular language in the question decidable? I tried for some time and cannot find a mischievous encoding that does so...
user21820
CC BY-SA 4.0
2020-09-28T08:17:34.960Z
@user21820 Here is the simplest I can think of. Let $f$ be the constant $0$ function, let $\{M_{2n}:n\in\mathbb N\}$ be an enumeration of Turing machines that accept $0$, and $\{M_{2n+1}:n\in\mathbb N\}$ an enumeration of Turing machines that do not accept $0$, and put $\langle M_n\rangle=n$. Then $\{\langle M\rangle:M\text{ accepts }f(\langle M\rangle)\}=\{n:n\text{ even}\}$ is decidable.
Emil Jeřábek
CC BY-SA 4.0
2020-09-28T08:54:52.367Z
@EmilJeřábek: Sorry, that was not the question I wanted to ask. I wanted to ask if there is a single encoding such that $L_f$ is decidable for every computable $f$. Even in the special case where $f$ is the identity function, I was unable to find an encoding that works.
user21820
CC BY-SA 4.0
2020-09-28T09:44:16.663Z
I’m pretty sure you can do it for the identity. For *all* computable $f$ at once, that sounds unlikely.
Emil Jeřábek
CC BY-SA 4.0
2020-09-28T10:14:56.790Z
No, wait. If $f(n)=n$, then $L_f$ is always undecidable: otherwise there is $M$ that accepts exactly the complement of $L_f$, and then $\def\<#1>{\langle#1\rangle}\<M>\in L_f\iff M \text{ accepts }\<M>\iff\<M>\notin L_f$, a contradiction. I believe the same argument can be adapted to all *injective* computable $f$. However, for most sufficiently non-injective computable $f$, one can make $L_f$ decidable (individually). For example, assume that $f(2n)=f(2n+1)$ for all $n$, and define an enumeration of TM by induction so that $M_{2n}$ is the lexicographically first as yet unenumerated TM ...
Emil Jeřábek
CC BY-SA 4.0
2020-09-28T10:17:16.550Z
... that accepts $f(2n)=f(2n+1)$, and $M_{2n+1}$ the first unenumerated TM that does not accept $f(2n)=f(2n+1)$. It is easy to see that all TM are eventually enumerated, and then this enumeration (with $\langle M_n\rangle=n$) makes $L_f$ the set of even numbers as above.
Emil Jeřábek
CC BY-SA 4.0
2020-09-28T16:07:55.793Z
@EmilJeřábek: Thanks! No wonder I couldn't find an encoding! That was kind of surprising; it felt possible. =)
user21820
CC BY-SA 4.0
2020-09-28T16:35:16.943Z
@user21820 I expanded my last two comments to an answer, giving a complete classification of $f$ such that the decidability of $L_f$ depends on the encoding.
Emil Jeřábek
CC BY-SA 4.0
2020-09-20T20:20:18.380Z
2020-09-21T21:19:41.220Z
2020-09-21T21:19:41.220Z
Aryeh
<p>For a given computable <span class="math-container">$f$</span>, the decidability of <span class="math-container">$L_f$</span> is independent of the encoding of Turing machines if and only <span class="math-container">$f$</span> is eventually injective (i.e., there exists a finite <span class="math-container">$X\subseteq\def\N{\mathbb N}\N$</span> such that <span class="math-container">$f\restriction(\N\smallsetminus X)$</span> is injective, or equivalently, <span class="math-container">$\{\def\&lt;#1&gt;{\langle#1\rangle}\&lt;n,m&gt;:n\ne m,f(n)=f(m)\}$</span> is finite).</p>
<ol>
<li><strong>If <span class="math-container">$f$</span> is computable and eventually injective, then <span class="math-container">$L_f$</span> is undecidable for any encoding.</strong></li>
</ol>
<p>Assume for contradiction that <span class="math-container">$L_f$</span> is decidable. Then
<span class="math-container">$$\{m\in\N:\exists n\in\N\:(f(n)=m\land n\notin L_f)\}$$</span>
is r.e., hence it is accepted by infinitely many Turing machines; in particular, using the assumption, it is accepted by a TM <span class="math-container">$M$</span> such that <span class="math-container">$f(n)\ne f(\&lt;M&gt;)$</span> for all <span class="math-container">$n\ne\&lt;M&gt;$</span>. Then
<span class="math-container">$$\&lt;M&gt;\in L_f\iff M\text{ accepts }f(\&lt;M&gt;)\iff\&lt;M&gt;\notin L_f,$$</span>
a contradiction.</p>
<ol start="2">
<li><strong>If <span class="math-container">$f$</span> is not eventually injective, then the decidability of <span class="math-container">$L_f$</span> depends on the encoding.</strong></li>
</ol>
<p>As shown in Aryeh’s answer, <span class="math-container">$L_f$</span> is undecidable under the standard encoding, hence it suffices to exhibit an encoding that makes <span class="math-container">$L_f$</span> is decidable. Let <span class="math-container">$\{M_m:m\in\N\}$</span> be any enumeration of TMs, and define <span class="math-container">$X\subseteq\N$</span> by
<span class="math-container">$$n\in X\iff|\{m&lt;n:f(n)=f(m)\}|\text{ is even.}$$</span>
We define a new enumeration <span class="math-container">$\{M'_n:n\in\N\}$</span> by
<span class="math-container">$M'_n=M_{m(n)}$</span>, where <span class="math-container">$m(n)$</span> is defined by induction on <span class="math-container">$n$</span>:
<span class="math-container">$$m(n)=\begin{cases}
  \min\bigl\{m\in\N\smallsetminus\{m(i):i&lt;n\}:M_m\text{ accepts }f(n)\bigr\},&amp;\text{if }n\in X,\\
  \min\bigl\{m\in\N\smallsetminus\{m(i):i&lt;n\}:M_m\text{ does not accept }f(n)\bigr\},&amp;\text{if }n\notin X.
\end{cases}$$</span>
To see that <span class="math-container">$\{M'_n:n\in\N\}$</span> indeed enumerates all TMs, assume for contradiction that <span class="math-container">$m$</span> is least such that <span class="math-container">$m\ne m(n)$</span> for all <span class="math-container">$n\in\N$</span>. Since <span class="math-container">$f$</span> is not eventually injective, there are <span class="math-container">$n&lt;n'$</span> such that <span class="math-container">$f(n)=f(n')$</span> and <span class="math-container">$\{0,\dots,m-1\}\subseteq\{m(i):i&lt;n\}$</span>. We may assume <span class="math-container">$n'&gt;n$</span> is smallest such that <span class="math-container">$f(n')=f(n)$</span>, which implies
<span class="math-container">$$n\in X\iff n'\notin X.$$</span>
Thus, either <span class="math-container">$n''=n$</span> or <span class="math-container">$n''=n'$</span> satisfies
<span class="math-container">$$M_m\text{ accepts }f(n'')\iff n''\in X,$$</span>
which implies <span class="math-container">$m(n'')=m$</span> by the definition of <span class="math-container">$m(n'')$</span>, a contradiction.</p>
<p>Thus, we may define an encoding of TM by <span class="math-container">$\&lt;M'_n&gt;=n$</span>, and then it follows from the definition that
<span class="math-container">$$L_f=X,$$</span>
which is decidable.</p>
<hr />
<p>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.</p>
<p>Anyway, if we allow non-injective encodings, the answer is that the decidability of <span class="math-container">$L_f$</span> depends on the encoding for <em>every</em> <span class="math-container">$f$</span>: it is undecidable under the standard encoding by Aryeh’s answer, while it is trivially decidable (because finite) for the constant encoding <span class="math-container">$\&lt;M&gt;=0$</span>.</p>

CC BY-SA 4.0
2020-09-28T17:06:52.980Z
Nice! Thanks for the illuminating answer! =)
user21820
CC BY-SA 4.0
2020-09-28T16:32:59.900Z
2020-09-28T18:08:24.407Z
2020-09-28T18:08:24.407Z
Emil Jeřábek
<p>Let <span class="math-container">$f : \{0, 1\}^* \to \{0, 1\}^*$</span> be a computable function. Given any encoding <span class="math-container">$\left&lt;M\right&gt;$</span> of Turing machines over binary (i.e., a function from the set of Turing machines to the set of strings over <span class="math-container">$\{0, 1\}^*$</span>), consider the following language:</p>
<p><span class="math-container">$$ L_f = \{\left&lt;M\right&gt; \mid M \mathrm{\ accepts\ } f(\left&lt;M\right&gt;)\} $$</span></p>
<p><strong>Question:</strong> Does there exist a function <span class="math-container">$f$</span> for which the decidability/recognizability of this  language depends upon the particular encoding used?</p>

<turing-machines><decidability>
Dependence of decidability on the encoding of Turing machines
RandomStudent
# Dependence of decidability on the encoding of Turing machines

(Asked by: username_0 on 2020-09-20)

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?

**Tags:** turing-machines, decidability

---

## 2 answers

### Answer by username_1 on 2020-09-20. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, this is interesting. Didn't know the Recursion theorem before.  
> **username_2**: This does not work for arbitrary encodings, but only for those that satisfy the recursion theorem.  
> **username_1**: What are the conditions for an encoding to satisfy the recursion theorem?  
> **username_2**: [Admissible numberings](https://en.wikipedia.org/wiki/Admissible_numbering) 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”.  
> **username_1**: 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?  
> **username_1**: A minimal property you want an encoding to satisfy is that two non-equivalent objects don't get mapped to the same string.  
> **username_1**: What else can you impose, at that level of abstraction?  
> **username_2**: Well, there are all kinds of things you might impose. E.g., you can impose that various constructions on Turing machines are computable; in particular, the s-m-n theorem (given an encoding of a Turing machine and an input, you can compute an encoding of the corresponding Turing machine where that input is hard-wired). Or, you can impose that there is a universal Turing machine: i.e., $U$ such that $U(\langle M\rangle,x)\simeq M(x)$.  
> **username_1**: Ah yes—in our course we do precisely the latter. We state it as a theorem and majorly handwave the proof. I guess mischief can occur here if careless.  
> **username_3**: @EmilJeřábek: Can you actually prove that there is some bad encoding that makes this particular language in the question decidable? I tried for some time and cannot find a mischievous encoding that does so...  
> **username_2**: @user21820 Here is the simplest I can think of. Let $f$ be the constant $0$ function, let $\{M_{2n}:n\in\mathbb N\}$ be an enumeration of Turing machines that accept $0$, and $\{M_{2n+1}:n\in\mathbb N\}$ an enumeration of Turing machines that do not accept $0$, and put $\langle M_n\rangle=n$. Then $\{\langle M\rangle:M\text{ accepts }f(\langle M\rangle)\}=\{n:n\text{ even}\}$ is decidable.  
> **username_3**: @EmilJeřábek: Sorry, that was not the question I wanted to ask. I wanted to ask if there is a single encoding such that $L_f$ is decidable for every computable $f$. Even in the special case where $f$ is the identity function, I was unable to find an encoding that works.  
> **username_2**: I’m pretty sure you can do it for the identity. For *all* computable $f$ at once, that sounds unlikely.  
> **username_2**: No, wait. If $f(n)=n$, then $L_f$ is always undecidable: otherwise there is $M$ that accepts exactly the complement of $L_f$, and then $\def\<#1>{\langle#1\rangle}\<M>\in L_f\iff M \text{ accepts }\<M>\iff\<M>\notin L_f$, a contradiction. I believe the same argument can be adapted to all *injective* computable $f$. However, for most sufficiently non-injective computable $f$, one can make $L_f$ decidable (individually). For example, assume that $f(2n)=f(2n+1)$ for all $n$, and define an enumeration of TM by induction so that $M_{2n}$ is the lexicographically first as yet unenumerated TM ...  
> **username_2**: ... that accepts $f(2n)=f(2n+1)$, and $M_{2n+1}$ the first unenumerated TM that does not accept $f(2n)=f(2n+1)$. It is easy to see that all TM are eventually enumerated, and then this enumeration (with $\langle M_n\rangle=n$) makes $L_f$ the set of even numbers as above.  
> **username_3**: @EmilJeřábek: Thanks! No wonder I couldn't find an encoding! That was kind of surprising; it felt possible. =)  
> **username_2**: @user21820 I expanded my last two comments to an answer, giving a complete classification of $f$ such that the decidability of $L_f$ depends on the encoding.  

---

### Answer by username_2 on 2020-09-28. Score: 5

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.

2. **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$.

> **Comments:**
> **username_3**: Nice! Thanks for the illuminating answer! =)  

---

