Cheap and Secure Web Hosting Provider : See Now

[Solved]: Extension of Rice's theorem

, , No Comments
Problem Detail: 

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable")

Asked By : shiva

Answered By : babou

Any property $P$ of a pair of RE sets becomes a property $P_{1,B_0}$ of the first component alone, if we fix the second RE set to a set $B_0$. As such, by Rice theorem, the property $P_{1,B_0}$ must be trivial or undecidable. If it is undecidable, then the property $P$ is undecidable for $\{(A,B_0)\mid A\in RE\}$, and is thus also undecidable for $\{(A,B)\mid A,B\in RE\}$. If it is trivial, it is either true or false for all $A\in RE$, and thus $P$ is either true for all pairs in $\{(A,B_0)\mid A\in RE\}$, or false for all of them.

We assume that it is trivial, and without loss of generality that it is true for all pairs $(A,B_0)$.

There are then two possibilities:

  • There is some RE set $A_0$ such that the property is undecidable for the set of pairs $\{(A_0,B)\mid B\in RE\}$, where $B$ is any RE language. This implies, as before, that it is a fortiori undecidable for the set of all pairs of RE languages.

  • For any choice of $A_0$, the property $P$ is decidable over $\{(A_0,B)\mid B\in RE\}$. Since $A_0$ is fixed, it can be viewed as a decidable property $P_{2,A_0}$ on the second component alone, which may be any RE set. Hence by Rice theorem, it is trivial. So $P_{2,A_0}(B)$ is either true, or false, for all choices of $B\in RE$. Hence the property $P$ is trivial, either true or false, over the set $\{(A_0,B)\mid B\in RE\}$. Since it is true for all pairs $(A,B_0)$, it must be true for $(A_0,B_0)$, and since it is trivial for $\{(A_0,B)\mid B\in RE\}$, it must be true for all pairs $P(A_0,B)$. And since that reasonning is valid for any choice of $A_0$ in RE, the property must be true for all pairs of RE sets.

Hence we see that the property is either undecidable or trivial (true for all pairs or false for all pairs).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29713

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback