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

Question

25-04-2020
Computers and Technology

contestada

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

Respuesta :

Otras preguntas

What is the initial value of the equation shown? y = −7x − 6 −13 −7 −6 −1

“Belief in God is the most important Muslim belief.” Discuss this statement showing that you have considered more than one point of view. (You must refer to rel

Congress enacted a statute appropriating money to the states on condition that the states use the money to support "public performances of classical ballet open

A 0.410 cm diameter plastic sphere, used in a static electricity demonstration, has a uniformly distributed 35.0 pC charge on its surface. What is the potential

The knowledge of latitude and longitude is important for people . Give 3 reasons ?

When you hear good news from a friend but you only give them a mild smile and do not make a big deal out of the news which response style is this and what is th

According to Dante, who built the Gate of Hell?

what is the energy now stored if the capacitor was disconnected from the potential source before the separation of the plates was changed

Find the equation of a line parallel to −x+5y=1 that contains the point (−1,2)

If you touch a surface, you leave behind millions of bacteria and other microbes. If each person’s community of microbes is unique, this bacterial smudge could

adebayodeborah8 adebayodeborah8 · Answer 1 · 2020-04-26T09:40:58+02:00

adebayodeborah8 adebayodeborah8

26-04-2020

Answer:

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.

Answer Link