Given a language: $A = \{ <M> | M\ rejects\ the\ string\ "101" \}$

Can I prove it is undecidable using Rice's theorem?

See like the theorem conditions are met (there exists non trivial language that describes the machine language )

  • $\begingroup$ Do you mean "undecidable"? (Rice's theorem shows undecidability, not decidability). $\endgroup$ – Shaull May 15 '17 at 11:20
  • $\begingroup$ Yes - fixed now. $\endgroup$ – Homem Gustavo May 15 '17 at 11:22
  • 1
    $\begingroup$ So, if you think the conditions are met - what's the question? $\endgroup$ – Shaull May 15 '17 at 11:31
  • $\begingroup$ I know that you cannot apply rice theorem when a machine constrain is set (in this case , the machine must reject) is it true? Is the proof ok? $\endgroup$ – Homem Gustavo May 15 '17 at 11:42
  • $\begingroup$ Just check whether or not the conditions of Rice's theorem hold. There's nothing more to it. $\endgroup$ – David Richerby May 15 '17 at 12:46

Rice's theorem says that any nontrivial semantic property of TMs is undecidable. The property in question is clearly nontrivial, but let's see if it's semantic.

A semantic property of TMs is a set of TMs $P$ such that for every two TMs $M_1,M_2$, if $L(M_1)=L(M_2)$ then either $M_1,M_2\in P$ or $M_1,M_2\notin P$. That is, membership in $P$ is determined only by the language, and not by the "inner workings" of the machine.

In this case, since "rejecting" and "never halting" are the same thing from the point of view of the language, then the property is not semantic. That is, there can be two machines with the same language, where one rejects 101, and the other doesn't halt on 101.

So no, you can't use Rice's theorem here.

  • $\begingroup$ The word semantic should be replaced with the word extensional. $\endgroup$ – Andrej Bauer May 15 '17 at 14:37
  • $\begingroup$ @AndrejBauer - why? Semantic properties are a very standard term for this. Also, they really are semantic, as they refer to the language, rather than the specific structure. $\endgroup$ – Shaull May 15 '17 at 14:57
  • $\begingroup$ By calling extensional properties semantic you are implicitly stating that the meaning of a Turing machine is its extensional behavior (i.e., what outputs it yields on various inputs). But I beg to differ. The natural semantics of a Turing machine is its operational behavior, i.e, it is important how Turing machines calculate outputs. If you use the word extensional then there is no question about what semantics of Turing machines you might have in mind. It is clear that we are talking about the extensional behavior of machines, i.e., what outputs they produce on given inputs. $\endgroup$ – Andrej Bauer May 15 '17 at 15:12
  • $\begingroup$ It's an interesting discussion, probably the wrong place for it. Anyway, IMO the semantics is indeed the output. If you want to "see" the operational behaviour, then work with transducers that output the name of the current state, for example. Indeed, if you take two different TMs, you cannot compare them based on their behaviour, since their structures may be completely different (e.g. have different state names). The fact that TMs actually have accept/reject states is so that there is a "meaning" to the computation, which is not the computation itself. $\endgroup$ – Shaull May 15 '17 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.