4
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Raphael May 27 '16 at 12:08
  • 1
    $\begingroup$ I thaught that's what check-my-answer/proof tags are for.. but I'm willing to delete this question if you wish $\endgroup$ – Uria Mor May 27 '16 at 12:15
  • $\begingroup$ 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. $\endgroup$ – Raphael May 27 '16 at 12:26
  • 2
    $\begingroup$ 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". $\endgroup$ – D.W. May 27 '16 at 19:00
  • $\begingroup$ 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. $\endgroup$ – Uria Mor May 28 '16 at 7:41
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Uria Mor May 27 '16 at 11:59
  • $\begingroup$ @UriaMor yes and I provided a simple explanation $\endgroup$ – Don Fanucci May 27 '16 at 12:11
  • $\begingroup$ You are right... didn't notice at start $\endgroup$ – Uria Mor May 27 '16 at 12:16
  • $\begingroup$ can you explain the line " there are languges in RE that do not compute a computable function because they are not decidable"? $\endgroup$ – Uria Mor May 27 '16 at 13:24
  • $\begingroup$ @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 $\endgroup$ – Don Fanucci May 27 '16 at 13:38

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.