Talk:Recursively enumerable language
From Wikipedia, the free encyclopedia
Would be nice to have an example of a recursively enumerable language on this page. Perhaps one that is not recursive.
Sorry those of you who noticed that Recursively Enumerable Languages were closed under homomorphism for a few minutes. I meant to stick that under Recursive but clicked the wrong link. No harm done, I hope...
I think recursively enumerable languages and sets should be explained/defined in terms of partial recursive or recursive functions (not with the vague term "algorithm")
I don't have the time right now. - Stephan Wehner
Note: What is the first definition and where is L? What if the first definition goes to language M directly. Copying from a book doesn't work in this case! OR COPY ALL OF IT!!!
- This "question" was pasted into the article by: 129.8.2.164. -- RTC 00:00 May 1, 2003 (UTC)
Attempted to clear up the references. Still, the definitions should be made more precise, but I don't have the time. (None of this is copied from a book!) - Stephan Wehner
- Good. I certainly didn't consider it copied and really felt that 129.8.2.164's "question" was 1/3 question 1/3 rant and 1/3 inability to read what was already written in the article (and on top of that pasting it in the article instead of asking it here was totally inappropriate). The answers to his question seemed reasonably clear to me, if one read the article, but due to the article's technical nature I didn't want to "mess" with it and risk mangling it accidentally :-) -- RTC 16:07 May 2, 2003 (UTC)
[edit] recursively enumerable set
How much of this material should be moved to recursively enumerable set? Michael Hardy 21:22, 30 Sep 2003 (UTC)
- I think most of it. I will give it a try, now that I expanded recursively enumerable set. As always feel free to improve upon my edits Michael. MathMartin 21:28, 8 Nov 2004 (UTC)
[edit] Complete rewrite
I did a rewrite of the page. I based the definition on recursively enumerable set and made it consistent with recursive language.
I deleted the following proof
- The equivalence of these two definitions can be seen as follows:
- 1 -> 2 Given an algorithm A according to the first definition for language L (assumed to be non-empty), the following algorithm will enumerate L according to the second definition: Let E be an algorithm which enumerates all strings, and so that every string appears infinitely often in the enumeration. We write E(n) to denote the string produced by algorithm E on input n. Pick a fixed string t in L (possible since L is non-empty). The following algorithm enumerates L:
- Given integer n, run algorithm A on input E(n) for n steps. If the answer is YES, output the string E(n). Otherwise, output string t.
- This algorithm will only output strings from L, and it will output all of them, since for every string s in L we can find an integer n which is greater than the number of steps that A needs to accept s and such that E(n) = s.
- 2 -> 1 Given an algorithm A according to the second definition for language L, the following algorithm will answer the question whether a given string s belongs to L in the sense of the first definition:
- For all numbers n, starting with 1, and continuing in sequence, test whether the string produced by algorithm A on input n is equal to s. When the first such n is found, output YES. (Otherwise, continue the LOOP)
I do not think it adds value to the article. Perhaps it should be integrated into the more general recursively enumerable set.MathMartin 15:33, 9 Nov 2004 (UTC)
