Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem.

Well I did show that with reduction, by using $HP'$.

Simply by creating a function from $f(\langle M \rangle, x) = (M')$

Thus, if $M$ stops on $x$ then $M'$ simulates the machine that stops on the empty word and accepts/rejects like it.

$(\langle M \rangle, x) \in HP' \rightarrow M$ rejects every input$ \rightarrow \langle M' \rangle \in L_2$

$(\langle M \rangle, x) \notin HP' \rightarrow M$ halts on $x \rightarrow L(M') = \phi $(it stops only on the empty word) $ \rightarrow \langle M' \rangle \notin L_2$

EDIT: In other words, can I just say that there're languages that contains $L$ thus $\in RE$ and languages that don't contain $L$ thus $\notin RE$. For example $L_{\phi \cup \sum^*\cup L_1}$ or just $L_1$. And $L_1$ is defined as a language that accepts all the languages with at least 200 words for example. Will this work for the Rice's theorem?

  • $\begingroup$ You have been asking a couple of similar questions in quick succession. Instead of having random strangers online do or review your homework for you, you should consider engaging fellow students or teachers. $\endgroup$
    – Raphael
    Mar 1 '18 at 18:09
  • $\begingroup$ @Raphael I see, thanks for your input. But I'm trying to solve the questions as much as possible before posting here. I'm constantly asking my friends about computability, but they can't answer this correctly sometimes so I want to make sure it's correct. $\endgroup$ Mar 1 '18 at 22:19
  • $\begingroup$ What are $L_\phi$, $L_{\{\Sigma^*\}}$ $HP'$? Don't asume that everybody is familiar with the notation that your course or textbook uses. What's $M'$? What's $L_2$? How does "Thus, if $M$ stops on $x$, then..." follow from what you wrote before? Sorry, but this isn't really making any sense. $\endgroup$ Mar 1 '18 at 23:23
  • $\begingroup$ The empty language(reject any input), the language that accepts any input, The halting problem that halts on string that's not in the language. $M'$ is a machine I build to run other $TM$ machines, $L_2$ is $L$ $\endgroup$ Mar 1 '18 at 23:33

Rice's theorem only proves undecidability, not un-semi-decidability. There is a variant that does that, but that has other conditions (obviously).

  • $\begingroup$ By variant you mean just showing the $\phi$ is in the property $S$, thus it's not in $RE$? Which we can say after proving it's not in $R$. because $\phi$ is definitely in $L$. $\endgroup$ Mar 1 '18 at 22:21
  • 1
    $\begingroup$ @IlanAizelmanWS Sorry, but your comment makes no sense to me at all. I can't tell what you're trying to say. You keep writing symbols without saying what they mean. $\endgroup$ Mar 1 '18 at 23:25
  • $\begingroup$ @DavidRicherby If the empty set in the property, thus we can say it's not in $RE$. $\endgroup$ Mar 1 '18 at 23:35
  • 1
    $\begingroup$ Oh. The emptyset is \emptyset ($\emptyset$). $\phi$ is a Greek letter. But what do you mean by "showing the empty set is in the property S?" and "the empty set is definitely in $L$"? Isn't $L$ a language? Languages are sets of strings, not sets of sets. $\endgroup$ Mar 1 '18 at 23:37

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.