<p>This question is probably more suitable in cs.se, but until it gets migrated, here is an answer.</p>

<p>Rice's theorem regards non-trivial <em>semantic</em> properties.</p>

<p>Formally, a semantic property is a set of Turing machines $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 solely by the language of the machine, and not by its "inner working".</p>

<p>Rice's theorem states that for every such property $P$ that is nontrivial (so it is not empty, nor contains every machine), it holds that deciding membership in $P$ is undecidable.</p>

<p>EDIT per the OP's request:</p>

<p>An intuitive way to look at a semantic property is that it only concerns <em>what</em> a program does, rather than <em>how</em> it does it. That is -  memory management, pointers, data, types, etc - are all syntactic, in a way, and thus are <strong>not</strong> semantic properties. This is because for every program you can build a different program that works entirely differently, but achieves the same result. </p>

<p>Semantic properties only look at the "output" of the program (in cases where this is well-defined).</p>

<p>Thus, your intuition is incorrect. None of the internal workings of a program are subject to Rice's theorem, exactly because if you change entirely the inner workings (while maintaining the output), then either both programs should have the property, or both should not have them.</p>

CC BY-SA 3.0
2015-05-02T19:11:22.597Z
You didn't comment on the correctness of my speculation. Also, your answer doesn't meet my requested criteria! As requested in the question, I'm seeking a more "intuitive" explanation rather than such formal and hard to comprehend explanations. Thanks anyway though.
Seyed Mohammad
CC BY-SA 3.0
2015-05-02T19:54:26.610Z
Edited. I hope it will be clearer now. By the way, I'm pretty sure the down vote is because this question is not research-level. It is a perfectly valid question for cs.se, though, and will probably be migrated there.
Shaull
CC BY-SA 3.0
2015-05-03T03:36:40.753Z
Thanks for the edit. This is helpful. One last thing is can you also provide a "supporting reference" for this explanation? I mean something worth to be cited which supports this explanation and provides complementary discussions.
Seyed Mohammad
CC BY-SA 3.0
2015-05-03T05:56:47.423Z
I don't know of any reference to this. I think the reason is that Rice's theorem shows such a fundamental result for TMs, that there is no motivation to examine it under the light of RAM machines, or programming languages, since these are "harder" cases.
Shaull
CC BY-SA 3.0
2015-05-02T12:12:44.593Z
2015-05-02T19:54:06.993Z
2015-05-02T19:54:06.993Z
Shaull
<p>This is a question that arose when studying Rice's theorem. As you all might know, Rice's theorem (informally and simply) states:</p>

<blockquote>
  <p>"There is no Turing machine (i.e. program) that can always (or generally) decide whether the language of another given Turing machine (i.e. program) satisfies a particular nontrivial property".</p>
</blockquote>

<p>Some real examples of these nontrivial properties are:</p>

<ul>
<li>Does a given program eventually halt for all possible inputs? (Turing's halting problem)</li>
<li>Are all accesses to an array in a given program inside the array's bounds? (buffer-overflow/overrun)</li>
<li>Is a given C program free of "use-after-free" bugs? (using a pointer after releasing it)</li>
</ul>

<p>But there are also some other nontrivial properties for programs that can be decided using other programs (for example, compilers):</p>

<ul>
<li>Are all the function invocations in a program previously defined? (Detecting undefined function invocations)</li>
<li>Are all the variables in a program initialized?</li>
<li>Do all assignment operations in a program, satisfy type-safety? (Detecting incompatible types assignments)</li>
</ul>

<p>So it seems that not all nontrivial properties are the subject of Rice's undecidability theorem. An explanation in <a href="http://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow">the Wikipedia article</a> states:</p>

<blockquote>
  <p>"It is important to note that Rice's theorem does not say anything about those properties of machines or programs that are not also properties of functions and languages."</p>
</blockquote>

<p>Unfortunately, this explanation didn't exactly help me understand the distinguishing aspect of properties that are subject of Rice's theorem from those properties that aren't.</p>

<p>Further down the Wikipedia article, it restates the matter like this:</p>

<blockquote>
  <p>"There exists no automatic method that decides with generality non-trivial questions on the <strong>behavior of computer programs</strong>."</p>
</blockquote>

<p>My speculation from the term <strong>"program behavior"</strong>, and additionally by observing the example properties, is that <strong>any nontrivial property that is related to the program's runtime data, is the subject of Rice's theorem</strong> (e.g. array indexing, pointer lifetime, halting, ...). In contrast, properties that are unrelated to the program's runtime data are not subject to Rice's theorem (e.g. type-safety, function definitions, variable initialization, ...). Note that I'm assuming "variable initialization" to be static data, not dynamic runtime data.</p>

<p><strong>How correct or accurate is my speculation?</strong> If I'm mistaken then, is there <strong>an intuitive and concise explanation</strong> on the distinguishing aspects of properties that are subject to Rice's theorem from those that are not?</p>

<p>By "intuitive and concise" I mean an explanation suitable for a one session presentation of Rice's theorem to an audience of higher-undergrads and grad students of CS.</p>

CC BY-SA 3.0
2015-05-02T19:12:25.310Z
**@DownVoter** It would be more constructive to provide a reason for a down-vote ...
Seyed Mohammad
CC BY-SA 3.0
2015-05-03T02:05:44.740Z
Based on the tip @Shaull gave, I referred to http://cstheory.stackexchange.com/help/on-topic and I realize that my question doesn't exactly fit the intended topics of this Q/A site. I acknowledge this isn't a research question, but it's not a typical undergrad discussion either, thus my mistake!
Seyed Mohammad
CC BY-SA 3.0
2015-05-03T06:22:30.210Z
**@Moderators:** I would migrate the question to cs.stackexchange If I could, but I can't. So how about performing a migrate instead of a hold?
Seyed Mohammad
<undecidability>
How to distinguish the properties applicable to Rice's theorem?
Seyed Mohammad
# How to distinguish the properties applicable to Rice's theorem?

(Asked by: username_0 on 2015-05-02)

This is a question that arose when studying Rice's theorem. As you all might know, Rice's theorem (informally and simply) states:

> "There is no Turing machine (i.e. program) that can always (or generally) decide whether the language of another given Turing machine (i.e. program) satisfies a particular nontrivial property".

Some real examples of these nontrivial properties are:

* Does a given program eventually halt for all possible inputs? (Turing's halting problem)
* Are all accesses to an array in a given program inside the array's bounds? (buffer-overflow/overrun)
* Is a given C program free of "use-after-free" bugs? (using a pointer after releasing it)

But there are also some other nontrivial properties for programs that can be decided using other programs (for example, compilers):

* Are all the function invocations in a program previously defined? (Detecting undefined function invocations)
* Are all the variables in a program initialized?
* Do all assignment operations in a program, satisfy type-safety? (Detecting incompatible types assignments)

So it seems that not all nontrivial properties are the subject of Rice's undecidability theorem. An explanation in [the Wikipedia article](http://en.wikipedia.org/wiki/Rice%27s_theorem) states:

> "It is important to note that Rice's theorem does not say anything about those properties of machines or programs that are not also properties of functions and languages."

Unfortunately, this explanation didn't exactly help me understand the distinguishing aspect of properties that are subject of Rice's theorem from those properties that aren't.

Further down the Wikipedia article, it restates the matter like this:

> "There exists no automatic method that decides with generality non-trivial questions on the **behavior of computer programs**."

My speculation from the term **"program behavior"**, and additionally by observing the example properties, is that **any nontrivial property that is related to the program's runtime data, is the subject of Rice's theorem** (e.g. array indexing, pointer lifetime, halting, ...). In contrast, properties that are unrelated to the program's runtime data are not subject to Rice's theorem (e.g. type-safety, function definitions, variable initialization, ...). Note that I'm assuming "variable initialization" to be static data, not dynamic runtime data.

**How correct or accurate is my speculation?** If I'm mistaken then, is there **an intuitive and concise explanation** on the distinguishing aspects of properties that are subject to Rice's theorem from those that are not?

By "intuitive and concise" I mean an explanation suitable for a one session presentation of Rice's theorem to an audience of higher-undergrads and grad students of CS.

**Tags:** undecidability
> **Comments:**
> **username_0**: **@DownVoter** It would be more constructive to provide a reason for a down-vote ...  
> **username_0**: Based on the tip @Shaull gave, I referred to http://cstheory.stackexchange.com/help/on-topic and I realize that my question doesn't exactly fit the intended topics of this Q/A site. I acknowledge this isn't a research question, but it's not a typical undergrad discussion either, thus my mistake!  
> **username_0**: **@Moderators:** I would migrate the question to cs.stackexchange If I could, but I can't. So how about performing a migrate instead of a hold?  

---

## 1 answers

### Answer by username_1 on 2015-05-02. Score: 1

This question is probably more suitable in cs.se, but until it gets migrated, here is an answer.

Rice's theorem regards non-trivial *semantic* properties.

Formally, a semantic property is a set of Turing machines $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 solely by the language of the machine, and not by its "inner working".

Rice's theorem states that for every such property $P$ that is nontrivial (so it is not empty, nor contains every machine), it holds that deciding membership in $P$ is undecidable.

EDIT per the OP's request:

An intuitive way to look at a semantic property is that it only concerns *what* a program does, rather than *how* it does it. That is - memory management, pointers, data, types, etc - are all syntactic, in a way, and thus are **not** semantic properties. This is because for every program you can build a different program that works entirely differently, but achieves the same result.

Semantic properties only look at the "output" of the program (in cases where this is well-defined).

Thus, your intuition is incorrect. None of the internal workings of a program are subject to Rice's theorem, exactly because if you change entirely the inner workings (while maintaining the output), then either both programs should have the property, or both should not have them.

> **Comments:**
> **username_0**: You didn't comment on the correctness of my speculation. Also, your answer doesn't meet my requested criteria! As requested in the question, I'm seeking a more "intuitive" explanation rather than such formal and hard to comprehend explanations. Thanks anyway though.  
> **username_1**: Edited. I hope it will be clearer now. By the way, I'm pretty sure the down vote is because this question is not research-level. It is a perfectly valid question for cs.se, though, and will probably be migrated there.  
> **username_0**: Thanks for the edit. This is helpful. One last thing is can you also provide a "supporting reference" for this explanation? I mean something worth to be cited which supports this explanation and provides complementary discussions.  
> **username_1**: I don't know of any reference to this. I think the reason is that Rice's theorem shows such a fundamental result for TMs, that there is no motivation to examine it under the light of RAM machines, or programming languages, since these are "harder" cases.  

---

