Watch Complete Explanation of “Rice Theorem for Programs” here:
https://youtu.be/92BkNvlGNyY
My answer is specifically for option C.
Option C : A Turing machine computes the products of two numbers.
The question is not asking if there exist a TM which can do the product of two numbers. Instead, it is asking that "Given any arbitrary TM, does it compute the product of two numbers ?"
This is undecidable.
Rice’s Theorem says that testing any non-trivial semantic property of a Turing machine is undecidable, where a semantic property depends only on whether the machine halts or produces a particular output for each input, and not on the details of the computation, and a property is non-trivial if there is at least one machine for which it holds and at least one for which it doesn’t.
Property "computes the product of two numbers" is :
1. Semantic Property :
Because a semantic property depends only on whether the machine halts or produces a particular output for each input, and not on the details of the computation.
Here, in the problem of finding if "Given any arbitrary TM, does it compute the product of two numbers ?" , we only bother about producing a particular output for each input, and not on the details of the computation. i.e. we do not care how the computation internally goes on i.e. we do not care whether machine takes 400 steps Or machine has 30 states Or machine never moves to the left etc.
2. Non-trivial property :
Because a property is non-trivial if there is at least one machine for which it holds and at least one for which it doesn’t. Clearly, there are TMs which do not compute the product of two numbers and there are TMs which do compute product of two numbers.
So, by Rice's theorem, testing any non-trivial semantic property of a Turing machine is undecidable.
Note that Rice’s Theorem is only about inputs and outputs. There are non-semantic properties (like “does this machine run in polynomial time on input x?” or “are the first 3 bits of <M> 011?”) that are easily decidable even though they are non-trivial. It also only works because we consider machines that might not halt.
Rice Theorem for Programs, Complete Explanation
Watch the following playlist on “Undecidability and Countability”, Rice Theorem:
https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI