I'm trying to prove that TM = DFA is undecidable using reduction from Halting Problem Theoretically I understand that Turing Machine captures all the computable functions and DFA only capture the functions that can be computed in constant space therefore TM = DFA is undecidable.
Here are my steps: Suppose that R that decide L(M)=L(D)
EQ_DM = { [D,M] | L(M) = L(D) }
and we create a turing machine
HALT_TM = { [M,w] | (M halt on input w→Accept
M did not halt on input w→Reject)}
How do I construct a D & M so R[D,M] tells if M halt on w?
Suppose that it is decidable whether a TM and a DFA accept the same language. You can use this to solve the halting problem for a general TM.
Given any TM M and word w, construct M' so that whenever M enters the halt-reject state, M' enters the halt-accept state. Now, M' is a TM that accepts every string that causes M to halt. Now construct M'' from M' so that L(M'') is the intersection of L(M') and {w}, where w is any word. You can always construct M'' using the Cartesian product machine construction given a DFA for {w} and M'.
Since it is decidable whether L(M'') is equal to that of a DFA - say, the DFA for {w} - we can say whether M'' accepts {w}. If it accepts w, then L(M') contains w and if L(M') contains w, M halts on w. If M'' does not accept w, L(M') does not contain w and, therefore, M does not halt on w.