# Tag Info

37

For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output ...

36

Fundamental misunderstanding: Every property of a computer program is non-computable That is not what Rice's theorem talks about. It talks about properties of functions and that the set of programs computing this function is not decidable. Formally, given $\emptyset \subset P \subset \mathsf{RE}$ the set $\qquad \displaystyle \{ \langle M \rangle \mid ... 13 The language$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$is not an index set, that is it is not of the form$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$for some set of (partial recursive) functions$P$, with$f_M$the (partial) function computed by TM$M$. Rice's theorem ... 13 All recognisable languages are recognised by a TM with an even number of states, so the property is trivial. If a language is recognisable, there is (by definition) a TM that recognises it. If it happens to have an even number of states, then you're done. If it has an odd number of states, add another state that doesn't do anything (or duplicates an ... 12 A "trivial" property is one that holds either for all languages or for none. 11 Your misunderstanding is: 'sure' in the sense of being computationally verified by an algorithm We are not, and we can not be . The question, Is this given Turing machine$M$a universal one? can not be generally and algorithmically decided for the reasons you state. However, we can prove for a fixed Turing machine that it is universal -- and that ... 9 This is somewhat of a trick question. What you are missing is that there are no uncountable languages over a finite (or even countable) alphabet. This should be enough information to answer it. (I initially gave the entire answer away, but edited it out after considering a bit.) 8 This is called the reachability problem -- is it possible for a given system to enter a given state? Techniques that attempt to answer this problem fall under reachability analysis, which is one of the main goals of (finite / symbolic) model checking. As the other answer suggests, this is one of the many instances covered by Rice's theorem. Answering ... 7 Undecidable means not decidable. Undecidable problems may or may not be semi-decidable. To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems.... 7 In the context of Rice's theorem, a class of languages is trivial if either it contains all RE languages; it contains no RE languages. In your case, the language is trivial for the first reason, as Luke explains. 6 The Rice theorem says that you can't tell anything about the ultimate behavior of a program when it is left to run to infinity - no matter how you classify programs, there will be two programs that will converge to the same ultimate behavior (computed function) although you classified them differently. But letting the programs run to infinity is essential. ... 6 The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM$M$belongs to the set, and$N$is a TM equivalent to$M$, then the encoding of$N$must also belong to the set. Equivalence here means that the TMs$M,N$terminate on the same inputs,... 5 I'm not sure I understand your confusion (feel free to expand, if you are still confused), but there two issues that might give you better intuition: Given a Specific TM$M$, we can know for sure'' what it does for all inputs. This is not "sure" in an algorithmic way, but sure in an absolute (mathematical) way. Example: Consider the TM that has one ... 5 First, the words in your language aren't encodings of machines, they contain more information, so you can't directly apply Rice theorem. That said, Rice's theorem talks about the impossibility of reasoning about the function computed by a Turing machine (namely, whether it lies in some set$S$). This is not the case here, since as Raphael mentioned, there ... 5 An undecidable property$\pi$of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying$\pi$. We identify the property with the language of encodings of Turing machines satisfying the property. The fact that a language is undecidable just means that no Turing machine decides the language — this is ... 5 A property that holds for every machine or holds for none is trivial. Rice's theorem does not apply to such a property. To see why, note that such a property can be decided by a very simple Turing machine, which accepts/rejects every Turing machine representation. 5 EDIT: This answer is more detailed than mine. This is an example of a question covered by Rice's theorem. For example, the question of if a program outputs "Hello World" or not is covered by that theorem. It also covers quantification over inputs (e.g. does program$P$do$X$on all input, does program$P$do$X$on some inputs, does program$P$do$X$on ... 4 Rice's theorem states that you can't decide a non-trivial property of Turing Machines in general. You are asking, "given a specific Turing Machine, can I find some property about it." The answer is yes in a large number of cases. Rice's Theorem says there's no algorithm which can look at any Turing Machine and find its optimum. Your problem is to look at ... 4 The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem. Assume$L$is decidable. Suppose I am asked whether a TM$M$accepts$w$. I will construct a machine$M'$which on input$x$checks if$x=\langle M' \rangle$. If it is not$\...

4

Almost The correct answer is that a property of recursive languages is r.e. if and only if it can be verified by a finite number of values (though unlike in your example the exact number of values can be unbounded, so $k$ can depend on $n$). In fact, the wikipedia page for Rice's theorem has a section on this: ...the analogue says that if one can ...

4

Let us verify that $S$ is a decider for $A_{\text{TM}} = \{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\}$. Let $⟨M,w⟩\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification. First, construc $M_w$. Since $M$ accepts $w$, $M_w$ simulate $T$. Use TM $R_P$ to determine whether $⟨M_w⟩ \in P$. Since $M_w$ simulate $... 4 You said in a comment: I am talking to process this encoding, not the tape content. But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape. You want to "go through all encoded transitions ... 3 Rice's theorem says that, for any nontrivial set$\mathcal{L}$of languages, the set of Turing machines that recognize a language in$\mathcal{L}$is undecidable. Wikipedia says that a specific language is decidable. So there's no contradiction. 3 There is some TM which is not in$L'$, and there is some TM which is in$L'$. So the definition of$L'$determines a nontrivial property on r.e. languages and so by Rice's theorem it is not decidable. 3 A "property" is simply a subset of languages in$RE$-- the set of all the languages that "satisfy" that property. A non-trivial property$P$is a non-empty set$P$which is strictly contained in$RE$, that is$\emptyset \subset P\subset RE$. It means there is at least one RE language that doesn't satisfy$P$, and at least one RE language that does satisfy ... 3 Rice's theorem cannot be used to show the undecidability of these two languages. Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: A property is a class of Turing-... 3 You are estimating that processes at an oil refinery are computable -- that may very well be true. However, it's unlikely that they are Turing-complete. Unless they are, Rice's theorem does not apply. 3 If when you say "$M$is a$LBA$(or$DFA$or$PDA$)" you mean that$M$has a fixed decidable structure (i.e. some properties of its internal state/transition structure) that forces its behaviour to be like a$LBA$(or$DFA$or$PDA$) then Rice's theorem cannot be applied directly. For example, if "$M$is a$DFA$", is formally defined as "$M\$ has no left ...

3

As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.

2

Hint. We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that, if they do halt, they cycle through all their states just before doing so. This gives you a class of TMs that visit every state if and only if they halt.

Only top voted, non community-wiki answers of a minimum length are eligible