Jeffrey Posted November 2, 2010 Share Posted November 2, 2010 In Dhruv's GRECS wiki, http://grecs.wikispaces.com/ , there is a TM question "Will this TM finish computing before sunset if it were to start before sunrise on the same day? ", which is said to be undecidable. I think the sentence is equivalent to " Will this TM accept a certain string within 'k' steps?" And I guess it's decidable, since it's very like "Will a TM halt within 'k' steps?" ,and maybe it's a subset of this one. The expression like "before sunset" which emphasizes time rather than "steps" is weird. Most of the textbooks and questions use "steps", since every step definied in a TM is a limited number of actions that can be done within a given time, which implies that "time" is equivalent to "step" in a sense. I've talked to Dhruv, and we want to get help from urch and experts. Just as he said, the CSGRE is notorious for asking questions that are slightly different from the ones you may already have encountered. So, "Will this TM finish computing before sunset if it were to start before sunrise on the same day? ", decidable or undecidable? Quote Link to comment Share on other sites More sharing options...
Jeffrey Posted November 4, 2010 Author Share Posted November 4, 2010 Dhruv's explanation about this TM question in grecs wiki is correct. The similar question is question 94 in titaniumbits booklet. Quote Link to comment Share on other sites More sharing options...
itman Posted November 9, 2011 Share Posted November 9, 2011 Actually, it wasn't and he corrected it. IMHO, Question 94 in TB has nothing to do with this problem, because it implies a Turing-incomplete lang. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.