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

Question

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?

Answer 1

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

Answer 2

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