I need to prove that a Turing Machine that only accepts even length strings in undecidable.
The proof I was thinking is explaining the following: Given an input that contains even length strings, if the string is even you can mark it with a special character '$', if it is odd mark it with special character '#', what if the string is infinitely long? then there would be no way to mark it as either even or odd, which would make this TM undecidable.
Am I on the right track with this proof?
I appreciate any suggestions.
Many thanks in advance!
Best Answer
The problem with your original proof is that strings are by definition finite in the context of formal languages, though languages can be infinite... If you decide to go the route of a reduction then take care that your reduction is 1) the right way, 2) has any closure properties you are looking for: eg. many-to-one vs. turing wrt. closure by complementation, 3) is truly a reduction in that solutions for A must exist iff (pay attention to the inner iff) solutions exist on the other side of the reduction $$ A \leq_m B \iff \exists f \in rec :(x \in A \iff f(x) \in B).$$
Bit of a spoiler, but sounds like a good candidate for Rice's Theorem:
Let $P$ be a property of languages over $\Sigma = \{0,1\}^*$ such that $P \neq \emptyset$ and $P \neq \Sigma^*$. Then $$ X = \{ <M> | M \text{ is a TM that decides a language with property}\; P \} $$ is undecidable.
http://en.wikipedia.org/wiki/Rice's_theorem