Proving that a Turing Machine that only accepts even length strings is undecidable

Question

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!

Answer 1

To prove that your Turing Machine is undecidable, you must construct a decider for it and show that if your decider works (this will lead to a contradiction, so a proof by contradiction is used), then a known undecidable problem could also be decided as a result. Three known undecidable TMs related to your problem are the "Turing Machine that accepts a certain string w", the "Turing machine that accepts no strings (empty set)", and the "Turing machine whose language is a regular language (i.e. has an equivalent finite automaton)".

For example, for the "Turing machine that halts on input w" problem, we can show that it is undecidable because if we had a decider for it, then the "Turing machine that accepts a certain string w" would be decidable as well; a contradiction. This is so because if we had some way to detect whether a Turing Machine halts on input, then the Turing machine could simply reject when it loops, or accept if the input is the wanted string w; thus becoming a decider as opposed to a recognizer. Since this decider would ultimately help us construct a decider for a known undecidable problem, it cannot exist; thereby proving that our original problem is undecidable.

I know it's very confusing. Took me a while to understand it.

Answer 2

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

Answer 3

As TonyK pointed out in a comment, it doesn't make sense to say that a Turing machine is undecidable (or decidable). My best guess is that the problem should have been to show that the collection of (Gödel numbers of) Turing machines that accept only even-length strings is an undecidable set. In other words, there is no algorithm which, given as input a Turing-machine program, determines whether that machine accepts only even-length strings. If this is indeed the problem, then I agree with everybodyelse that Rice's theorem provides a solution.