A language is undecidable if there is no Turing Machine that will recognize that language and halt on all inputs. Show that the following language is undecidable: A = {M | M is a Turing machine that accepts exactly all the odd length strings} The intended solution is to reduce from the halting problem, which we will show is undecidable. The halting problem is given a Turing machine M and an input w, decide whether M terminates when given w as input.