reduction technique for undecidability
To prove that problem X is undecidable you can reduce a problem Y (which has already been proved to be undecidable) to X. In fact if Y&lt;mX then we know that X is at least as much hard as Y is. So what you have to do is to show a function f that maps instances of problem Y in instances of problem X, so that if y is an instance of Y with answer "yes" than f(y)=x is an instance of problem X with answer "yes", and if y is an instance of Y with answer "no" than f(y)=x is an instance of problem X with answer "no".