This is the solution in the book Introduction to Theory of computation by Sisper to prove that regural TM is undecidable.
PROOF We let R be a TM that decides REGULARTM and construct TM S to
decide ATM. Then S works in the following manner.
S = “On input (M,W), where M is a TM and w is a string:
1. Construct the following TM M2.
M2 = “On input x:
1. If x has the form 0n1n, accept .
2. If x does not have this form, run M on input w and
accept if M accepts w.”
2. Run R on input (M,w).
3. If R accepts, accept ; if R rejects, reject .”
I can't seem to understand the logic. in 1.2 how can we run M on input w when we know that ATM is undecidable.And can someone please explain me the logic of this solution.
Submit an article or tip