# Decidability of the TM's computing a non-empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function and } f_M\in S \}$$

where $f_M$ is the function $M$ computes.

Prove that for every such none-trivial $S$, $L_S \notin \mathcal{R}$.

I tried to construct

• $L_{f}=\left\{ x\#y\in{\Sigma^*}|y=f\left(x\right)\right\}$
• $\tilde{S}=\left\{ L_{f}|f\in S\right\}$
• $L_{\tilde{S}}=\left\{ \left\langle M\right\rangle |L\left\langle M\right\rangle \in\tilde{S}\right\}$

and then show with Rice that $L_{\tilde{S}} \notin \mathcal{R}$, when the idea behind it was to eventually show that $L_{\tilde{S}} \leq_m L_S$. But the problem here is that I couldn't show a mapping reduction from $L_{\tilde{S}}$ to $L_S$ without assuming $L_{\tilde{S}} \in \mathcal{RE}$ (which I'm quite sure is not true).
So any other directions will be warmly welcomed!

• This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. – Raphael May 27 '16 at 12:08
• I thaught that's what check-my-answer/proof tags are for.. but I'm willing to delete this question if you wish – Uria Mor May 27 '16 at 12:15
• The tag is there, as is c. Doesn't mean we like most questions. I'd rather you make your question good than delete it. – Raphael May 27 '16 at 12:26
• The tag exists to warn you that this kind of question is generally unsuitable. When you select the tag, a one-sentence tag overview pops up, saying "Questions asking us to check whether your solution is correct are considered off-topic and should not be posted on this site". – D.W. May 27 '16 at 19:00
• Didn't see the popup probably because of the browser I'm using wouldn't show it. I edited according to your comments. Thanke you @D.W. – Uria Mor May 28 '16 at 7:41

For any function $f: \Sigma^* \rightarrow \Sigma^*$, let

$$L_f = \{ x \# y \mid y = f(x) \}$$

For any Turing machine $M$, we can construct the description of a Turing machine $M'$ such that $M'$ recognizes $L_f$ if and only if $M$ computes $f$. $M'$ will receive a string, check that it is of the form $x \# y$ and then simulate $M$ with input $x$. If the simulation returns $w$, $M'$ accepts if $w = y$. Therefore, the language

$$A_f = \{ \langle M \rangle \mid M \text{ is a TM that computes the function f} \}$$

reduces to the language

$$B_f = \{\langle M \rangle \mid L(M) = L_f \}$$

The class

$$L_S = \{ L_f \mid f \in S \}$$

is a nontrivial class of Turing-recognizable languages and therefore the decision problem $B_f$ is undedicable by Rice's theorem.

Assume WLOG* $Id\in S$ ($\forall x\in\Sigma^*:\ Id\left(x\right)=x$)

Define $f\left(\left\langle M,w\right\rangle \right)\mapsto\left\langle M'\right\rangle$ where $M'$ is a TM that on input x:

• if $M$ halts on $w$ then $M'$ accept (leave $x$ on the tape)

if $\left\langle M,w\right\rangle \in H_{TM}$ then $M'$ halts on every $x$ and the content of the tape by the end of the run is $x$ ($M'$ computes $Id$) - $\left\langle M'\right\rangle \in F$

if $\left\langle M,w\right\rangle \notin H_{TM}$ then $M'$ never halts hence $\left\langle M'\right\rangle \notin F$.

Since $H_{TM}\leq_m L_{S}$ and $H_{TM}\notin\mathcal{R}$ we have $L_{S}\notin\mathcal{R}$.

WLOG*: if $Id\notin S$ prove for $\overline{S}=F\smallsetminus S$ - since now $Id\in\overline{S}$ the same proof holds, so $L_{\overline{S}}\notin\mathcal{R} L_{\overline{S}}=\left\{ \left\langle M\right\rangle |f_{M}\notin S\right\}$ . Assume that $\overline{L_{S}}=\left\{ w\in\Sigma^*|\mbox{ if }w\mbox{ is an encoding of a TM then }w\mbox{ does not compute a function }f\in S\right\} \in\mathcal{R}$ and $R$ decides $\overline{L_{S}}$. We can construct a reduction f that on input $w$:

• if $R$ accepts $w$

• check if w is a TM encoding
• if w is a TM, accept
• reject

then $w\in\overline{L_{S}}$ iff $f\left(w\right)\in L_{\overline{S}}$ so we can decide $L_{\overline{S}}$ using $R$.

So $\overline{L_{S}}\notin\mathcal{R}\implies L_{S}\notin\mathcal{R}$

You can construct $$\ \mathcal{C}=\{L\in\mathcal{RE}\ |\ \exists f\in S \ \text{such that}\ \ \mathrm{Im} f=L\}$$ and it is clear That $$\emptyset \subset \mathcal{C}\subset \mathcal{RE}$$ (because it is a set of languages from $$\mathcal{RE}$$ and it is clearly not empty and there are languges in $$\mathcal{RE}$$ that do not compute a computable function because they are not decidable) and then by Rice's Theorem you get $$\{\langle M\rangle \ | \ L(M)\in\mathcal{C}\}\not \in \mathcal{R}$$ and this language is exactly $$L_S$$ so $$L_S \not \in \mathcal{R}$$.

• S is not in $\mathcal{RE}$ since it's not a set of languages.. Did you mean $\mathcal{C} \subset \mathcal{RE}$? I don't see that eighther – Uria Mor May 27 '16 at 11:59
• @UriaMor yes and I provided a simple explanation – Don Fanucci May 27 '16 at 12:11
• You are right... didn't notice at start – Uria Mor May 27 '16 at 12:16
• can you explain the line " there are languges in RE that do not compute a computable function because they are not decidable"? – Uria Mor May 27 '16 at 13:24
• @UriaMor remember that S is not trivial I'll explain why C!=RE so there is language in RE whose enumarator is a TM that writes the function that is not in S – Don Fanucci May 27 '16 at 13:38