1

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
    Commented 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 Raj
    Commented Dec 26, 2021 at 13:18

2 Answers 2

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 and acknowledge you have read our privacy policy.

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