Problem Detail: I’m seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea about what it means for two models of computation to be equivalent (the automata view: if they accept the same languages). Are there other ways of thinking about equivalence? If you could help me understand how to prove that the Turing-machine model is equivalent to lambda calculus, that would be sufficient.
Asked By : saadtaame
Answered By : Raphael
You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is). Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions are outlined. If you did this formally, you would take a general Turing machine (a tuple) and explicitly construct what the corresponding 2-PDA would be, and vice versa. Formally, such a simulation may look like this. Let $qquad displaystyle M = (Q,Sigma_I,Sigma_O,delta,q^*_1,Q_F)$ be a Turing machine (with one tape). Then, $qquad displaystyle A_M = (Q cup {q^*_1,q^*_2},Sigma_I,Sigma_O’, delta’, q_0, Q_F)$ with $Sigma_O’ = Sigma_O overset{.}{cup} {$}$ and $delta’$ given by $quad displaystyle (q^*_1,a,h_l,h_r) to_{delta’} (q^*_1,ah_l,h_r)$ for all $a in Sigma_I$ and $h_r,h_l in Sigma_O$,
$quad displaystyle (q^*_1,varepsilon,h_l,h_r) to_{delta’} (q^*_2,h_l,h_r)$ for all $h_r,h_l in Sigma_O$,
$quad displaystyle (q^*_2,varepsilon,h_l,h_r) to_{delta’} (q^*_2,varepsilon,h_lh_r)$ for all $h_r,h_l in Sigma_O$ with $h_l neq $$,
$quad displaystyle (q^*_2,varepsilon,$,h_r) to_{delta’} (q_0,$,h_r)$ for all $h_r in Sigma_O$,
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,varepsilon,h_la) iff (q,h_r) to_delta (q’,a,L)$ for all $q in Q$ and $h_l in Sigma_O$,
$quad displaystyle (q,varepsilon,$,h_r) to_{delta’} (q’,$,square a) iff (q,h_r) to_delta (q’,a,L)$ for all $q in Q$,
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,ah_l,varepsilon) iff (q,h_r) to_delta (q’,a,R)$ for all $q in Q, h_l in Sigma_O’$,
$quad displaystyle (q,varepsilon,h_l,$) to_{delta’} (q,h_l,square$)$ for all $q in Q$ and $h_l in Sigma_O’$, and
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,h_l,a) iff (q,h_r) to_delta (q’,a,N)$ for all $q in Q,h_linSigma_O’$ is an equivalent 2-PDA. Here, we assume that the Turing machine uses $square in Sigma_O$ as blank symbol, both stacks start with a marker $$notin Sigma_O$ (which is never removed) and $(q,a,h_l,h_r) to_{delta’} (q’,l_1dots l_i,r_1dots r_j)$ means that $A_M$ consumes input $a$, switches states from $q$ to $q’$ and updates the stacks like so:
[source] It remains to show that $A_M$ enters a final state on $x in Sigma_I^*$ if and only if $M$ does so. This is quite clear by construction; formally, you have to translate accepting runs on $M$ into accepting runs on $A_M$ and vice versa.
$quad displaystyle (q^*_1,varepsilon,h_l,h_r) to_{delta’} (q^*_2,h_l,h_r)$ for all $h_r,h_l in Sigma_O$,
$quad displaystyle (q^*_2,varepsilon,h_l,h_r) to_{delta’} (q^*_2,varepsilon,h_lh_r)$ for all $h_r,h_l in Sigma_O$ with $h_l neq $$,
$quad displaystyle (q^*_2,varepsilon,$,h_r) to_{delta’} (q_0,$,h_r)$ for all $h_r in Sigma_O$,
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,varepsilon,h_la) iff (q,h_r) to_delta (q’,a,L)$ for all $q in Q$ and $h_l in Sigma_O$,
$quad displaystyle (q,varepsilon,$,h_r) to_{delta’} (q’,$,square a) iff (q,h_r) to_delta (q’,a,L)$ for all $q in Q$,
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,ah_l,varepsilon) iff (q,h_r) to_delta (q’,a,R)$ for all $q in Q, h_l in Sigma_O’$,
$quad displaystyle (q,varepsilon,h_l,$) to_{delta’} (q,h_l,square$)$ for all $q in Q$ and $h_l in Sigma_O’$, and
$quad displaystyle (q,varepsilon,h_l,h_r) to_{delta’} (q’,h_l,a) iff (q,h_r) to_delta (q’,a,N)$ for all $q in Q,h_linSigma_O’$ is an equivalent 2-PDA. Here, we assume that the Turing machine uses $square in Sigma_O$ as blank symbol, both stacks start with a marker $$notin Sigma_O$ (which is never removed) and $(q,a,h_l,h_r) to_{delta’} (q’,l_1dots l_i,r_1dots r_j)$ means that $A_M$ consumes input $a$, switches states from $q$ to $q’$ and updates the stacks like so:
[source] It remains to show that $A_M$ enters a final state on $x in Sigma_I^*$ if and only if $M$ does so. This is quite clear by construction; formally, you have to translate accepting runs on $M$ into accepting runs on $A_M$ and vice versa.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3154
