# Questions tagged [rice-theorem]

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

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
56 views

### Proving that Rice's theorem does not apply to a property

This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic. The question is about if Rice theorem applies to certain ...
15 views

### Correct Turing machine representation for Rice Theorem proof

Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable). L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)} For example if I want to represent by diagram a TM $M_1$ ...
107 views

### How to show that the complement of ATM $\leq_{m}$ L = {<M> : |L(M)| = 2}?

My original intention was to prove that $L = \{\langle M \rangle \mid |L(M)| = 2 \}$ is not turing recognizable but soon I realized that I could use the complement of ATM because the complement of ...
105 views

### Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
53 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-...
### 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,...