[Undecidability] Understanding the proof of Rice's theorem

 
Picture of Θωμάς Παππάς
[Undecidability] Understanding the proof of Rice's theorem
by Θωμάς Παππάς - Friday, 7 February 2020, 2:06 PM
 

Hello everyone, I have a question regarding the proof of Rice's theorem.

First to make sure I've understood the basics. So the proof begins by trying to answer the Halting problem for an arbitrary input x, i.e. an arbitrary TM M with an arbitrary input y such that x = M;y. It then constructs the machine Mx is such a way that the language accepting Mx belongs to C.

The part that is not clear for me is how Mx and the "given TM M" of the theorem are connected. Is M the TM in x? Even then, Mx differs per different input.

From what I tried to understand of the proof, the reduction is from the question "For a TM M, does the language accepting M belong to C?" to the question "For an arbitrary TM M and an arbitrary input y, if M accepts y then does y belong in a language L in C?".

In other words (I think) the theorem tells us that is you want to ask a question for a property of a TM, you first need to go through the inputs. Therefore you first need to ask the question if that input is accepted or not by the TM and then see if it has any property, thus becoming dependend on answering the HALTING problem first (which then renders it undecidable).

Is the above argumentation valid? Thanks in advance for any comments!