How to find complement of L,
L = {<M>: M is a TM, which accepts some palindrome}
What is the general rule to finding a complement? I am thinking in this particular case it would be
L_bar = {<M_bar> : M_bar is a TM, which rejects any palindrome .???
The general rule for finding the complement (with respect to some understood universe U) of a language:
S = {x: P(x)}
, where x is an element of universe U and P(x) is true iff x has the property required for membership in S, is
S' = {x': ~P(x')}
, where x' is an element of universe U and ~P(x) is the negation of P(x) and is true iff x' does not have the property required for membership in S.
In your example:
L = {<M>: M is a TM, which accepts some palindrome}
We must first determine what the universe is. If we take the universe to be all strings which represent encodings of TMs, your answer is close but possibly not correct, depending on your definitions. It would be more unambiguously correct if you said "does not accept" instead of "rejects" since a TM could loop forever on a palindrome, never accepting or rejecting it.
If, on the other hand, the universe were TMs that halt on all inputs, your answer is correct. On the other other hand, if the universe were all binary strings, your answer would be wrong unless every possible binary string were a valid encoding of some TM in your encoding. If there were some encodings that weren't valid TMs, they would need to belong to the complement of L as well.