Ask Question
10 November, 17:14

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

+4
Answers (1)
  1. 10 November, 19:57
    0
    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.
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers