2
$\begingroup$

I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this:

TM M decides language L iff the strings in L put M into the Accept state and the strings NOT IN L put M into the Reject state

My problem is.. the strings "NOT IN L"? How can the definition be based on what's not in L? Shouldn't the definition be more like this?

TM M decides language L iff the strings L put M into the Accept state or the Reject state.

Then you can divide L into two subsets - those that are accepted, and those that aren't. But they're all decided by M, no?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @RanG. Good point. I'll take out the infinite part. My question still stands though :) $\endgroup$ – yts Nov 24 '14 at 3:34
  • 1
    $\begingroup$ The problem may be in the phrasing. M decides language L is a shorthand for TM M decides membership of language L, i.e. it takes an arbitrary string (whether in L or not) and outputs whether the string is in L. $\endgroup$ – reinierpost Nov 24 '14 at 8:43
  • $\begingroup$ A language is just a set of words. A machine decides a language if it always correctly determines set membership. $\endgroup$ – Tim Seguine Nov 24 '14 at 14:34
6
$\begingroup$

(I'll convert the comment into an answer)

First, definitions:

$L$ is a language, that is, a set of words where each word has a finite length. If all the words that ever exist are denoted as $\Sigma^*$ then any language is $L\subseteq \Sigma^*$. Words that are not in $L$ are in a different subset we denote $\overline L=\Sigma^*\setminus L$. Both $L$ and $\overline L$ can be infinite (i.e., have infinite many words). Still, each word in $L$ or in$\overline L$ is of finite length.

Now, assume that we have a TM that never goes into an infinite loop (such TMs are called deciders). If it never goes into a loop, it means that for any input word, it will either halt and accept or halt and reject.

If we used your second definition, then any $L$ will be $L=\Sigma^*$, since all the words are either accepted or rejected.

So the answer is that the first definition is correct. A decider $M$ (a TM that always halt!) splits the space of all the possible words $\Sigma^*$ into two disjoint subsets, the words that are accepted by $M$, denoted $L(M)$ and the ones rejected by $M$, denoted $\overline{L(M)}$. Again, $\Sigma^*=L(M) \cup \overline{L(M)}$, since every word is either accepted or rejected.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I appreciate your answer. I need to think about this a bit more, but can't right now. I'll get back to it. $\endgroup$ – yts Nov 24 '14 at 3:55
  • $\begingroup$ Thanks. I didn't realize that M deciding a language meant all words in ∑* would end up on accept or reject. When you said it's called a decider, I thought that was a special kind of TM, not synonymous with a TM that decides a language. $\endgroup$ – yts Nov 24 '14 at 15:12
3
$\begingroup$

You are right that $M$ makes a decision about every string, but this does not put them in $L$. Your second definition would lead to every (decidable) language being the same (any decider always ends up in a Reject or Accept state, so by the second definition every decider would decide every language).

To draw an analogy, take for example the language $English$, and the Turing Machine stand-in $Me$. If you present a word to me, I can decide (hopefully!) whether the word is in $English$ or not, but the words that make me say $No$ are not in $English$ - i.e. the language consists only of the words that are in it, it is not two sets (those that make me say $Yes$ and those that make me say $No$).

Going back to the maths, this is what the first definition says, but is a more precise manner appropriate for computability: the TM $M$ decides $L$ if for every string $\omega$ it says $Yes$ if $\omega \in L$ and $No$ if $\omega \notin L$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yeah, meant M. Fixed it $\endgroup$ – yts Nov 24 '14 at 5:34
  • $\begingroup$ My question is, if M decides a word with a reject, why is that word not part of the language M decides? Why is that word said to not be in L? $\endgroup$ – yts Nov 24 '14 at 5:36
  • $\begingroup$ @yts adjusted the answer a little. $\endgroup$ – Luke Mathieson Nov 24 '14 at 5:39
  • $\begingroup$ @yts, try thinking of it this way: $M$ is not deciding a word (because it isn't), $M$ is deciding whether the word is in $L$ or not (as this is what is actually meant). Saying $M$ decides $L$ is a somewhat awkward grammatical shorthand for this. $\endgroup$ – Luke Mathieson Nov 24 '14 at 5:41
  • $\begingroup$ Hold on. If a TM decides a language, that means that no matter what word in ∑* you give it, it will always either accept or reject. No word will loop. Is that a correct statement? $\endgroup$ – yts Nov 24 '14 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.