# Turing Machine Decidable: What right does the definition have to say what's not in language L?

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?

• @RanG. Good point. I'll take out the infinite part. My question still stands though :)
– yts
Nov 24, 2014 at 3:34
• 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. Nov 24, 2014 at 8:43
• A language is just a set of words. A machine decides a language if it always correctly determines set membership. Nov 24, 2014 at 14:34

(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.

– yts
Nov 24, 2014 at 3:55
• 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.
– yts
Nov 24, 2014 at 15:12

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$.

• Yeah, meant M. Fixed it
– yts
Nov 24, 2014 at 5:34
• 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?
– yts
Nov 24, 2014 at 5:36
• @yts adjusted the answer a little. Nov 24, 2014 at 5:39
• @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. Nov 24, 2014 at 5:41
• 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?
– yts
Nov 24, 2014 at 5:47