Consider an algorithm that accepts a Turing Machine M and constructs another Turing machine M2, such that L(M) $\neq$ L(M2). Show that such algorithm cannot exist.
My answer: If such algorithm exist, we could tell whether a Turing machine M accepts input w or not, as follows:
Construct a Turing machine X:
X receives input z if z equals 1 run M on input w if M accepts w X accepts z
Now we use the claimed algorithm to create machine X' that accepts a language different from L(X)
if M accepts w, the language of X is 1 and the language of X' is all strings, but 1
if M does not accept w, the language of X is every string in $\Sigma ^*$, but 1; and the language of X' is just 1
L(X) and L(X') complement each other
run both X and X', in parallel, on input 1 if X accepts 1, then M accepts w if X' accepts 1, then M does not accept w
We have solved an undecidable problem: the halting problem; thus contradicting the hypothesis of the existence of such algorithm.
Is this correct?
Thanks!
[Edited] As @mjqxxxx pointed out, my assumption that L(X') is the complement of L(X) is wrong. The problem only states that L(X') $\neq$ L(X).
Any hints on how to approach this proof?