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

Question

Computers & Technology

Frisco

1 November, 00:17

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

+3

Answers (1)

Know the Answer?

Martin Eaton · Answer 1

A is undecidable

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.