Talk:Recursive language

Example

I think that what's missing from this page is an example of a recursive language.

(a^n)(b^n)(c^n) is recursive. 128.84.152.179 17:39, 8 November 2006 (UTC)

Hopcroft & Ullman (1979 p.390) state that $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ is indexed. So while it is true that it's recursive, this isn't an example that's particularly unique to recursive languages. –jonsafari 22:22, 8 November 2006 (UTC)

In order to illustrate the place of recursive languages in the (extended) Chomsky hierarchy, could somebody please give an example for a recursive language that isn't context-sensitive? - Jochen Burghardt (talk) 19:35, 26 February 2015 (UTC)

You can take any language that provably requires more than linear space, see here [1]. For example, any EXPSPACE-complete language will do the job, see here [2]. An example that is easier to describe is the following language: $\{\,r\mid r{\mbox{ is a regular expression with negation over the alphabet }}\{a,b\}{\mbox{ and the language described by }}r{\mbox{ is empty}}\,\}$. This language is not in CSL (it is not even in ELEMENTARY). Hermel (talk) 22:05, 28 February 2015 (UTC)

Thank you. From the stackexchange links I understand that the Space hierarchy theorem implies the existence of recursive, but non-context-sensitive languages; I think this should be mentioned in the article. Apparently, a concrete language can't be given in a form as simple as, say, $\{a^{(2^{n})}b^{n!}c^{(n^{2})}|n\geq 1\}$. Your regular expression example is closest to that form; do you have a reference for it (which should also establish that the language is recursive)? - Jochen Burghardt (talk) 11:04, 10 March 2015 (UTC)

I looked again into this, and found another language, that is a bit easier to describe. In what follows, I refer to the original research paper

Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Symposium on Switching and Automata Theory (SWAT 1972), pp. 125–129. IEEE (1972)

and the survey

Markus Holzer and Martin Kutrib: "The Complexity of Regular(-Like) Expressions", in: Y. Gao et al. (Eds.): DLT 2010, LNCS 6224, pp. 16–30, 2010.

There are even notoriously difficult decision problems, whose associated language is context-sensitive. One such example is the inequivalence problem of regular expressions. More precisely, the set

$S_{1}=\{\,r\mid r{\mbox{ is a regular expression over the alphabet }}\{a,b\}{\mbox{ and }}r{\mbox{ does not describe all words in }}\{a,b\}^{*}\,\}$

can be decided by a LBA, and is therefore context-sensitive (cf. Theorem 15 in Holzer/Kutrib).

If we are looking for a language that is decidable but provably not context-sensitive, we need to look for a more difficult language. Assume now we extend the syntax of the usual regular expressions with the operations union, concatenation and Kleene star by adding the squaring operator ², with w² being a shorthand for ww. For example, we have (abba)²= abbaabba, ((abcab)²)²= abbaabbaabbaabba, and so on. Thus, there are regular expressions that can be described very succinctly using repeated squaring. We can transform a regular expression with squaring into an ordinary regular expression, but the length of the output can be exponential in the input length. Now consider the set

$S_{2}=\{\,r\mid r{\mbox{ is a regular expression with squaring over the alphabet }}\{a,b\}{\mbox{ and }}r{\mbox{ does not describe all words in }}\{a,b\}^{*}\,\}$

On one hand, the set $S_{2}$ is decidable. Namely, a Turing machine with output tape can transform a regular expression with squaring of length 'n' into an equivalent ordinary regular expression of length at most $2^{n}$. Then one can run a LBA whose input tape is the output tape of the previous Turing machine for deciding whether there is a word that is not described by the regular expression. Observe that the latter LBA requires space O(m), where $m\leq 2^{n}$ is the length of its input. Thus the set $S_{2}$ is recursive, and can be decided using space at most $O(m)=O(2^{n})$.

On the other hand, using techniques from computational complexity theory, one can prove that there is a constant 'c>1', such that the set $S_{2}$ cannot be computed by any nondeterministic Turing machine whose space bound is less than $c^{n}$ (cf. Theorem 2.1 in Stockmeyer/Meyer).

Most languages that can be given in a simple form as you mentioned can be computed in nondeterministic time $O(2^{n})$ and space $O(n)$. Notice that even NP-complete decision problems, such as 3SAT, are languages that can be accepted by some LBA. The little we know about separation of complexity classes makes it even more difficult to find a witness. For example, it is conjectured, but we cannot prove, that EXPTIME-complete languages are not context-sensitive. In order to have a chance of proving that a language is not in CSL, we have to resort to decision problems that are much more difficult. Another example of a decidable set, which is provably not context-sensitive, is the set of first-order formulas in Presburger arithmetic which are tautologies. Hermel (talk) 22:26, 10 March 2015 (UTC)

Attempt to merge

For anyone keeping this article on their watchlist: there is currently an attempt at merging a number of articles on (non-)recursive/(un)decidable/(un)computable sets/languages/decision problems into a single, thorough article. The experiment currently sits at Recursive languages and sets. Comments are very welcome. Pichpich (talk) 00:43, 21 February 2008 (UTC)

Revert

I just reverted an anonymous edit that added the following sentence: "Note: The set of all recursive languages can not be enumerated effectively. The proof is by diagonalization."

This is too ambiguous. Obviously this set can not be enumerated, some of its members are actually infinite. I believe what the author intended was something along the lines of "the set of all Turing machines that accept recursive languages is not recursively enumerable", or "the set of all Turing machines that are deciders is not recursively enumerable".

Anyway, such claims do not belong into the "closure properties" section, they should be stated more formally, and cite a suitable reference.

Misof (talk) 23:41, 29 September 2009 (UTC)

This article has inpenetrable complexity

The concept of "recursive language" is an important one for all programmers and they need to be able to understand it. The article as it currently reads sheds little or no light on this issue. For example SQL is a recursive language, and it is a language that virtually every programmer uses. These programmers should be able to read this article and understand the important aspects of recursive languages and how they are distinguished from procedural languages. This article might be too mathematical. I am not qualified to judge that aspect of it, but I suspect that this article is just wrong.--Jarhed (talk) 08:07, 25 June 2011 (UTC)

I don't think the article is wrong in general. The concept of recursive languages is a topic of theory and not a classification of programming languages (and could therefore be perceived less important for programmers). However, to help reduce the complexity of the article, you can try to explain what makes you think that SQL is a recursive language and what you would expect to read about in this article. --Zahnradzacken (talk) 11:02, 26 June 2011 (UTC)

I guess you are thinking of recursive queries. While there is ultimately some connection to the word recursive as used in in the originally mathematical term recursive language, this connection is so remote that you had better think of them as unconnected. I don't think we have an article on SQL recursive queries, and I don't know if we should have one. But it's clear that recursive languages in the mathematics / pure computer science sense are a much more important topic and that this article should not be hijacked for the SQL topic. Hans Adler 13:28, 26 June 2011 (UTC)

I am a programmer not a theorist. My understanding is that many languages were purposely designed to be recursive, such as Lisp (programming language), Smalltalk and SQL. When I read an article about "Recursive languages" I expect to be able to gain some understanding about the subject to know if this is true or not. This article is not sufficient for a knowledgeable reader such as me to gain any insight into the issue at all. If this article does *not* have any application to programming languages, it should make that clear. If it *does*, it should also make that clear. Thanks!Jarhed (talk) 02:30, 1 July 2011 (UTC)

The term “recursive language” refers to a specific class of formal languages (as in “regular language”, “context-free language” and so on), and its application to programming languages is very remote. (Specifically, a “recursive language” is not a programming language that supports recursion.) Do you have a suggestion how the article could make this clearer? — Tobias Bergemann (talk) 09:59, 1 July 2011 (UTC)

I wonder why you actually thought the terms were related. You wouldn't expect the Spanish language to be a programming language with Spanish keywords, and I haven't found a link from any programming language article to this one that could make you assume a relation. A recursively defined programming language uses recursive definition, a programming language supporting recursion need not be recursively defined (however, even regular languages can be recursively defined [reg langs being one of the most simple classes of formal languages, while programming languages are usually context-free languages]). Of course, if you stumble upon recursion, then get curious what the Recursive (disambiguation) is about and then end up here, you might read the article with false expectations. But doesn't the first sentence clarify that the term is derived from recursive sets? That's why I asked what made you think that SQL is recursive (not: recursively defined). The article should not be hijacked/bloated with all kinds of disclaimers what the article is not about (in particular it's not about natural languages, recursive jokes, ...). --Zahnradzacken (talk) 22:11, 4 July 2011 (UTC)

Thank you for your thoughtful reply. I suppose you have restated my point: I read the article and I could not make heads nor tails of it. My options are to a) assume that I am an idiot or b) assume that the article is opaque enough that a normally educated and aware reader cannot contextualize it. I went with b) and all I am suggesting is that you review this article for slight modification with a lay reader in mind. Thanks for your time.Jarhed (talk) 20:05, 13 July 2011 (UTC)

I know the feeling too well that some articles tend to make you choose option a. Obviously the article is written in a dense style but I think that's okay as long as the introduction clarifies the context. I believe that improving readability of such articles is much more work (though desirable) than having discussions like this one. Currently, I have no suggestion how to slightly modify the introduction without introducing negative statements ("Recursive languages are unrelated to ..."). What is your expectation of the first sentences, now that you probably know a bit more about the subject? Would it help if the article on recursive sets was more readable in order to grasp the context? --Zahnradzacken (talk) 21:19, 14 July 2011 (UTC)

I agree. There is a perfectly servicable introductory paragraph. It says: class of formal languages. What the heck is a formal language? That makes absolutely no sense.Jarhed (talk) 03:53, 16 July 2011 (UTC)

"Formal language" is defined in parentheses in the very first sentence of the article. In computer science terms: It's an arbitrary set of strings. Nothing more. No meaning attached whatsoever. This is a perfectly standard term in computer science, in mathematical logic and in linguistics, and anyone wo doesn't believe what he or she reads (I can understand why one wouldn't on first hearing that definition) can simply follow the link to formal language. Hans Adler 06:20, 16 July 2011 (UTC)

I agree that the treatment of formal language in the first paragraph is OK. Alas, computer science is rife with terms that have different meanings in different contexts. Along with "recursive", "algorithm" is another one. I took the liberty of slightly modifying this paragraph to add "algorithm" to the sentence about total Turing machines, since "algorithm" is very common usage for this concept in theoretical computer science. I do realize that this well-intended addition could also cause some confusion similar to what seems to have happened around the use of "recursive" here, but I did it for a good (at least in my opinion) reason. There is a debate about the term "algorithm" going on right now in the Talk page for another article in Wikipedia, and I intend to try to help resolve the debate and (more importantly) to improve that article. To do that, I needed this article to mention "algorithm" as it is commonly used in teaching theoretical computer science.

And by the way, I did note that the way I cited Prof. Sipser's textbook is not the way the moderators want us to do it, but I have not learned how to create proper citations yet. FWIW, it is on my to do list.

Mike-c-in-mv (talk) 23:08, 18 June 2023 (UTC)