"We cannot recognize a set of languages as the language themselves" What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
4
-
$\begingroup$ Can you please just give little concrete example if you people get time. Sorry If I am bothering you much and thanks in advance. $\endgroup$– Sameer RajCommented Dec 22, 2021 at 16:34
-
$\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources! $\endgroup$– D.W. ♦Commented Dec 23, 2021 at 5:12
-
$\begingroup$ Please credit the original source of all copied material. This is required under our rules: cs.stackexchange.com/help/referencing $\endgroup$– D.W. ♦Commented Dec 23, 2021 at 5:12
-
$\begingroup$ Yes. I will update this question as soon as I reach home. $\endgroup$– Sameer RajCommented Dec 26, 2021 at 13:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
TMs accept words as input.
What this paragraph is saying is that you cannot encode arbitrary languages as finite strings (aka words), and hence you cannot easily describe a property over languages themselves (for instance, a property of "all languages that contain the empty word", is a property over languages).
Afterwards it represents a way to somewhat describe some of the languages: a description of a language can be defined as "any turing machine accepting (computing) that language".
answered Dec 22, 2021 at 16:10
$\begingroup$
$\endgroup$
0
Admittedly, the sentence you give is indeed a trifle obscure. Simply said, it is saying that if we have a property of a language, like "any string in the language has odd length", we can't hope to recognize the property by using a TM that will iterate over all strings of all possible languages to test, since that would clearly be an infinite input, which we know is a TM no-no.
It goes on to state a definition that works, namely given a property, we can look instead at the set of all TM descriptions of machines which accept some language that has the property.
answered Dec 22, 2021 at 15:49