This possibility of Turing

machines looping forever leads us to define the notion

of a language recognizing. We say that a Turing machine

recognizes a language if and only if it accepts every

string in the language and does not accept any string

not in the language. Thus we can say that the turning

machine from the quiz does indeed recognize the language

consisting of strings that contain a 1. It accepts those containing a 1. And it doesn’t accept the others. Instead, it loops on them. Contrast this definition

with what it takes for a Turing machine to decide a language. Then, it must not only accept

every string in the language but it has to reject every

string not in the language. It can’t loop like this Turing machine. If we wanted to build a decider for

this language, we would need to modify

the Turing machine so that it detects the end of the string

and moves into the reject state like so. At this point, it also makes sense to

define the language of the machine. Which is just the language

that the machine recognizes. After all, every machine recognizes some

language even if it’s the empty one. Formally, we define L(M) to be

the set of strings that m accepts. That’s the language of the machine M.