Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

5
  • $\begingroup$ Other definitions of Turing machines generally do not require the TM to write "yes" or "no". Entering an accepting or rejecting state is sufficient. (Definitions are equivalent, though). "Crashed" is not standard terminology, and is misleading – "rejected" is better. $\endgroup$ Commented Jun 4, 2012 at 6:12
  • $\begingroup$ I am confused by the first transistions. Typically, a TM starts on the first input symbol, i.e. $\neq \Delta$ for non-empty inputs, so those TMs won't accept anything. Sadly, the document does not specify the semantics very carefully; have you checked other texts? $\endgroup$ Commented Jun 4, 2012 at 8:38
  • $\begingroup$ Yes, I learned it after my lecture. I read the text for more concrete examples. I still wonder what happens if the input contains symbols other than what is defined in a given alphabet. Halt and reject, maybe? $\endgroup$ Commented Jun 4, 2012 at 9:14
  • 1
    $\begingroup$ @Amumu: That can't happen by definition. That's the beauty of theory: closed world is not an assumption, but fact. In other words, the semantics of Turing machines are not even defined for words over an alphabet other than the TM's. $\endgroup$ Commented Jun 5, 2012 at 11:07
  • $\begingroup$ @Raphael Thanks for introducing the subject. Now it even makes more sense. $\endgroup$ Commented Jun 5, 2012 at 19:49