3
$\begingroup$

Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ 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<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\} $$

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

$\endgroup$
3
$\begingroup$

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<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\} $$ 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<M'\right>$ -- which it can, using the Recursion Theorem. Then, $M'$ runs $M_f$ with input $\left<M'\right>$, which tells it whether or not $M'$ is supposed to accept $f(\left<M'\right>)$. 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.

$\endgroup$
17
  • $\begingroup$ Thanks, this is interesting. Didn't know the Recursion theorem before. $\endgroup$ – RandomStudent Sep 21 '20 at 8:24
  • 1
    $\begingroup$ This does not work for arbitrary encodings, but only for those that satisfy the recursion theorem. $\endgroup$ – Emil Jeřábek Sep 21 '20 at 12:56
  • $\begingroup$ What are the conditions for an encoding to satisfy the recursion theorem? $\endgroup$ – Aryeh Sep 21 '20 at 12:58
  • $\begingroup$ 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”. $\endgroup$ – Emil Jeřábek Sep 21 '20 at 13:52
  • $\begingroup$ 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? $\endgroup$ – Aryeh Sep 21 '20 at 14:05
4
$\begingroup$

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,m>: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(\<M>)$ for all $n\ne\<M>$. Then $$\<M>\in L_f\iff M\text{ accepts }f(\<M>)\iff\<M>\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<n:f(n)=f(m)\}|\text{ is even.}$$ 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<n\}:M_m\text{ accepts }f(n)\bigr\},&\text{if }n\in X,\\ \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ does not accept }f(n)\bigr\},&\text{if }n\notin X. \end{cases}$$ 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<n'$ such that $f(n)=f(n')$ and $\{0,\dots,m-1\}\subseteq\{m(i):i<n\}$. 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 $\<M'_n>=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 $\<M>=0$.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.