When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".
Why this strange terminology?
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ I'm not quite sure what you're getting at. We call any set of strings a "language", so it seems straightforward to call the set of strings that happen to satisfy a predicate a "language". Are you asking why we call any set of strings a "language"? Or are you asking why in particular the set of strings that satisfies a predicate is a language? $\endgroup$– Eric LippertMar 16, 2018 at 22:19
-
$\begingroup$ @EricLippert, I didn't know that. In that case, my question is why any set of strings is called a language. $\endgroup$– user56834Mar 17, 2018 at 4:49
-
1$\begingroup$ I'm astonished that nobody here mentioned the Chomsky hierarchy, developed by the linguist Noam Chomsky. As you can see linguists were trynig to find some formal description for natural languages by using grammars. They ended up converging to computer science and hence the various concepts got mixed because they can indeed describe the same sets. $\endgroup$– BakuriuMar 17, 2018 at 12:30
-
1$\begingroup$ @Bakuriu 'I'm astonished that nobody here mentioned...' Why don't you change that by expanding on your comment by writing an answer? $\endgroup$– Discrete lizard ♦Mar 17, 2018 at 16:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
I believe a lot of this came out of linguistics research. People wanted to write down a formal description (grammar) of, e.g., the English language. By extension, the set of strings defined by any grammar is a language and, since unrestricted grammars are Turing-powerful, any computable set of strings is the language of some grammar.
answered Mar 16, 2018 at 19:10
-
1$\begingroup$ This is still useful today, of course. You can meaningfully talk about "The C language" or "The Python language," and computability theory can say various useful things about the parsing of said languages (e.g. is it regular? LL(1)? etc.). $\endgroup$– KevinMar 17, 2018 at 1:22
-
$\begingroup$ @Kevin Hmm, I'd say a 'programming language' more often is something fundamentally different in purpose than the usage of 'language' here. Sure, a 'programming language' can be seen as a set of strings, but usually people actually mean a form of specification of computer instructions, instead. But yes, sometimes regarding them as 'language' in the same sense as this question is useful. $\endgroup$– Discrete lizard ♦Mar 17, 2018 at 16:52
$\begingroup$
$\endgroup$
I think it is useful to note that most pioneering CS work, such as initial work by Turing and Church, had the intention to describe computation carried out by humans. (Recall that a computer was a human profession around that time!)
From this perspective, the set of strings that are output of a decision problem is the set of strings that a (precise and correct!) human 'computer' may 'utter' (i.e. output, most likely the computer would write his/her answers down).
Calling this set of strings that refers to structured, but human, communication a 'language' doesn't sound very far-fetched to me, so this could be a reason for the term.
My knowledge of history isn't good enough to check whether this is merely my interpretation or the common interpretation at the time, so take this with a grain of salt. Still, I hope this provides a reason to name the concept a 'language'.
answered Mar 16, 2018 at 20:56
$\begingroup$
$\endgroup$
From Wikipedia, “a formal language is a set of strings of symbols together with a set of rules that are specific to it.” To precisely specify what we are trying to decide, ambiguous natural languages won’t do, so instead mathematicians represent possible inputs with precise symbols. Together, the set of strings that result in Yes outputs comprise, in a poetic sense, the language of that problem, e.g., how 2, 3, 5, 7, and so on are the language of prime numbers.
Again according to Wikipedia
The first formal language is thought to be the one used by Gottlob Frege in his Begriffsschrift (1879), literally meaning “concept writing,” and which Frege described as a “formal language of pure thought.”
