Skip to main content

Questions tagged [rice-theorem]

Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
1 answer
1k views

Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
Ronit sharma's user avatar
1 vote
0 answers
49 views

How do you use Rice's theorem and why does it make sense? (Use provided Rice's theorem)

So this is the Rice's theorem we were provided: Definition: $TM$-$FUNC(S)$ Input: Turing machine $M$ Question: Is $f_M \in S$ Let $S$ be a set of computable partial functions with $\emptyset \neq S \...
Yuirike's user avatar
  • 29
1 vote
0 answers
55 views

Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
jase's user avatar
  • 11
1 vote
0 answers
50 views

Does description method matter in Rice’s theorem?

If $\mathcal{p}$ is a nontrivial property of formal languages, then $L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem. What if we describe ...
Omid Yaghoubi's user avatar
1 vote
0 answers
806 views

Rice theorem, the proof of the part when the empty language belongs to the property

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown. $...
Abhishek Ghosh's user avatar
0 votes
0 answers
43 views

Undecidability of a set of Turing Machines

Considering the following set, I have to say if it is undecidable, decidable or semidecidable: $$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
Filippo Scaramuzza's user avatar
0 votes
0 answers
40 views

Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...
user6394019's user avatar
0 votes
0 answers
31 views

Is my assumption about non trivial propery correct?

"make sure you understand why for a non trivial property $S$, $\bar{S}$ is also non trivial" My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and ...
user6394019's user avatar
0 votes
1 answer
225 views

Using Rice's theorem to prove undecidability of $E_{TM}$

I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$...
NimaJan's user avatar
  • 353
0 votes
0 answers
56 views

Is undecidability of TMs' properties a statistical statement?

We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-...
Jerome's user avatar
  • 109
0 votes
0 answers
62 views

Reduction without Rice's Theorem

How can I show that the following language is neither semi decidable nor co-semi decidable without using Rice's Theorem? Further for the following language, how would I show that it IS co-semi ...
Freelo's user avatar
  • 11
-2 votes
1 answer
47 views

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

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, ...
Ilan Aizelman WS's user avatar