1
$\begingroup$

enter image description here

"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?

$\endgroup$
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 Raj
    Dec 22 '21 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.
    Dec 23 '21 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.
    Dec 23 '21 at 5:12
  • $\begingroup$ Yes. I will update this question as soon as I reach home. $\endgroup$
    – Sameer Raj
    Dec 26 '21 at 13:18
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.