Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[Theoretical computer science] Regular Turing Machine undecidable proof

  1. Aug 22, 2015 #1
    Hello the proof of the Spiser's book (introduction to theory of computation):
    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?
  2. jcsd
  3. Aug 26, 2015 #2
    Could you be a little more clear on what this is trying to prove?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook