Talk:Recursively enumerable language

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)

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)

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)

Examples?

Is this examples of Recursively enumerable languages?

• The language of Halting turning machines.
• The language of valid formulae in first order logic.

Taemyr (talk) 13:00, 22 January 2008 (UTC)

I've read the page about inline citation and I don't understand why there is a message box about inline citation.

They are not required here, and I don't see any sentence that may be likely to be challanged; any of those assertion can be found in any text book or pdf teaching this subject. Hence giving an inline citation seems pretty hard since I could almost add every citation to every sentences.

Arthur MILCHIOR (talk) 02:32, 3 November 2013 (UTC)

"Turing recognizable" listed at Redirects for discussion

The redirect Turing recognizable has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2024 May 4 § Turing recognizable until a consensus is reached. 1234qwer1234qwer4 20:02, 4 May 2024 (UTC)