CODEWITHSUNDEEP
logicreductionturing-machinesdecidable
David
David

Reputation: 165

Direct Reduction, Turing machine and a DFA

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure how it totally works. lets see an example:

Given the language L:

L ={<M,D>| M is s TM and D is a DFA so that L(M) = L(D)},

using reduction how to prove Atm < L.

My solution:

M is a Turing machine that accepts any string and it halts on that string. D is DFA hast accepts the language L and its equivalent to TM M. Atm is a TM, M that accepts string w.

How can you prove using a direct reduction that Atm < L??

Upvotes: 1

Views: 853

Answers (1)

Patrick87
Patrick87

Reputation: 28312

We need to show that a decider for L can be used to decide instances of Atm, that is, a decider for L can be used to answer the question "does a given TM accept a given input string?"

Given an instance <M, w> of Atm, we need to transform it into an instance <M', D> of this problem so that a solution to this problem will answer the other.

First, construct M' so that L(M') = L(M) intersect {w}. This can be done as follows. Create a TM that scans the input tape and ensures that w is the input. If w is not the input, halt-reject. Otherwise, return to the front of the tape and transition to the formerly initial state of M. Then, run M as normal. Clearly, this can only possibly accept w, since we rejected everything else; and if M accepts w, this will as well, since after the initial phase M runs normally.

Second, construct D so that L(D) = {w}. This DFA will have |w| + 2 states: an initial state, a dead state, and one state per symbol in w.

Now, use our decider for L on the instance <M', D>. It will halt-accept if and only if L(M') = L(D) = {w}, which is only possible if L(M) intersect {w} = {w} which in turn is only satisfied if L(M) contains w. So if we halt-accept, then we have an answer to our instance <M, w> of Atm.

Upvotes: 1

Related Questions