Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
How can a Turing Machine be undecidable? – TonyK Mar 7 '13 at 17:26
If no Turing Machine decides it. Meaning, if it runs infinitely, and does not enter an accept or reject states (halt) for all input strings, it is undecidable. – Epsilon Mar 7 '13 at 17:30
I can easily write a Turing Machine that accepts finite even-length strings and rejects finite odd-length strings. Obviously if infinite input strings are allowed, the problem (not the Turing Machine!) becomes undecidable. But that is not how the term is usually employed. – TonyK Mar 7 '13 at 18:17
To put it briefly: according to the Wikipedia article on undecidable problems, "a decision problem is a subset of the natural numbers". So an infinitely long input string is not allowed, because it doesn't represent a natural number. – TonyK Mar 9 '13 at 17:16
The definition of "string" is usually "finite sequence of symbols", and the usual definition of Turing machine requires that the inputs be finite. And if you allow infinite inputs, then the problem seems to be with deciding whether the input is finite or infinite, not with deciding whether it's even or odd. So the parity issue is a red herring. To answer the question you asked, "Am I on the right track with this proof," I would say "No, you seem to be deeply confused." – MJD Mar 12 '13 at 12:53

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.'s_theorem

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.