Question

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 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

Answer 1

A is undecidable

Step-by-step explanation:

construct aTM TI that will accept on input x |X| is odd if |X| is even, it stimulates M on input w.

TI enters the reject state when M accept w. when M rejects w, T1 enters accept state.

Observe that if M accept W, then t1 is a turning machine that accepts all inputs of odds length. If M rejects or loops on input w, then T1 is a turning machine that rejects the loop.