Language Recognizers – Georgia Tech – Computability, Complexity, Theory: Computability

Language Recognizers – Georgia Tech – Computability, Complexity, Theory: Computability


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.

Leave a Reply

Your email address will not be published. Required fields are marked *