- #1
blob84
- 25
- 0
Hello the proof of the Spiser's book (introduction to theory of computation):
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 o^i 1^i , accept.
2. If x does not have this form, run M on input w and
accept if M accepts w."
2. R on input (M2 ).
3. Run R if accepts, accept; if R rejects, reject."
I don't understand how it works.
If x has that form accept and R will reject because 0^i1^i is not regular.
What happens when M rejects?
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 o^i 1^i , accept.
2. If x does not have this form, run M on input w and
accept if M accepts w."
2. R on input (M2 ).
3. Run R if accepts, accept; if R rejects, reject."
I don't understand how it works.
If x has that form accept and R will reject because 0^i1^i is not regular.
What happens when M rejects?