# Questions tagged [rice-theorem]

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

77 questions
Filter by
Sorted by
Tagged with
197 views

### Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps. Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps? I ...
• 223
1 vote
50 views

407 views

• 229
1 vote
62 views

### Is there a connection between the Undecidability Theorem and "software complexity"?

I was reading Complexity: The Emerging Science at the Edge of Order and Chaos and a certain passage got me really intrigued. When discussing Chris Langton's explorations of artificial life algorithms,...
295 views

### Halting (on empty input tape) for an infinite subset of all Turing machines

As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem. But what if, instead ...
• 155
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 ...
250 views

### Is Rice's Theorem equivalent to the Halting problem?

As I understand it Rice's Theorem seems to imply the existence of the Halting problem. That is, with Rice's Theorem, we can prove that the Halting problem is undecidable. However, to me, it seems like ...
1 vote
63 views

• 1,132
92 views

### EVEN-CFL Decidable / Undecidable - Rice-Theorem

Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$ Question : Is EVEN-CFL ...
• 51
275 views

### How can I apply Rice's theorem?

I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not. In one of the past exams, there was the following ...
• 199
211 views

### Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
• 1,677
248 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 ...
• 21
336 views

### Decidability of decision problems

Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ...
2k views

### Rice Theorem - Problem to understand and apply it

I have struggle to understand the Rice Theorem. My understanding of Rice Theorem: The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial ...
1 vote
350 views

### How to determine if this problem is decidable?

I am currently stuck on the following problem: Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times? My ...
1 vote
349 views

### Rice's Theorem - usage on $DFA$ or $LBA$

I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable. However I am not sure about one ...
• 315
171 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 (...
• 125
1 vote
129 views

### Rice's theorem applicable to the following language?

Let $L= \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle \}$ be a language where $\langle M \rangle$ is the Code of the TM $M$. $L$ is undecidable. I've heard that I can't use Rice's ...
• 223
2k views

### Language of TM is Undecidable

why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable? I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
• 223
1k views

### proof of the rice's theorem

Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given TM’s language has property $P$ is undecidable. Proof:(This is from sipser'...
• 253
380 views

### What is the Name of the Problem or Technique of Determining if a Line in a Program Will Execute

If I were to pose the question: "Given a program $P$ containing statement $X$, will $X$ be executed (given enough runs with all possible inputs)?" This strikes me of being a relative of the Halting ...
• 133
1 vote
507 views

### Trying to prove semidecidability of an undecidable language

I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...