most recent 30 from http://mathoverflow.net 2013-05-25T22:51:48Z http://mathoverflow.net/feeds/user/14878 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63902/regular-tm-is-undecidable gjb 2011-05-04T11:03:49Z 2012-04-30T20:31:15Z

<p>I'm sure you all are familiar with Theorem 5.3 from Sipser's TOC book:</p> <p>S = "On input (M,w) where M is a TM and w is a string: 1. Construct the code of TM M2 as follows: M2 = "On input x: (a) If x = 0n1n for some n ≥ 0, accept. (b) If x = 0n1n, run M on w and if M accepts w, then accept." 2. Run R on (M2). 3. If R accepts, accept; if R rejects, reject."</p> <p>I'm hoping to find an explanation as to how accepting (a) helps here. If x is of the form 0n1n then M2 accepts, R accepts, and S accepts. But we have accepted a nonregular language and M is not even considered. So R will accept this particular nonregular language (or)? epsilon star if M accepts w. Since R is obviously outside of M2 how does it know what caused M2 to accpet?</p> <p>Does anyone have a different perspective on this? All of my searches seem to simply regurgitate Theorem 5.3 and don't offer much else.</p>

http://mathoverflow.net/questions/63902/regular-tm-is-undecidable/63904#63904 gjb 2011-05-04T12:18:20Z 2011-05-04T12:18:20Z

I strove for a week or so to seek an understanding of this theorem and yet did not yield an understanding of this theorem. Thank you for your explanation Mr. Kontorovich. R accepts or rejects based on the language of M2.