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
1
vote
1answer
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 ...
0
votes
0answers
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$ ...
0
votes
0answers
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 ...
0
votes
2answers
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 (...
0
votes
0answers
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-...
0
votes
0answers
44 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 ...
-2
votes
1answer
35 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,...