Talk:Recursive languages and sets
From Wikipedia, the free encyclopedia
Please see the discussion started at Talk:Decision_problem#Merge_from_Undecidable_problem to understand why this experiment is taking place.
[edit] Choosing the right title
I wrote Recursive languages and sets at CBM's suggestion. While we're at it, we might want to make it Recursive/Decidable languages and sets. Not a sexy title, but at least covers the terminology completely and this will avoid gruesome fights between CS and math people. Pichpich (talk) 22:36, 20 February 2008 (UTC)
- I think that as long as the title has "sets" in it, it should be possible to sway the recursion theorists. The most stark difference is that "languages" vs. "sets" mentality (of course they are equivalent). — Carl (CBM · talk) 23:15, 20 February 2008 (UTC)
- Would then Decidable languages and sets be the better choice? Decidable is well understood by math people and I suspect that some of the literature in recursion theory uses this terminology anyways. For computer scientists who are not theory-educated, recursive might be a bit misleading. In any case, as I said previously, I don't think there'll be much of a hoopla if we keep listing the redirects in the appropriate categories. Pichpich (talk) 00:10, 21 February 2008 (UTC)
[edit] The right term
For this article, is it better to describe a computable set as computable or decidable? I slightly favor the latter. I strongly favor choosing one to use for the bulk of the article, while listing the synonyms in the lede. — Carl (CBM · talk) 23:15, 20 February 2008 (UTC)
- Very true. I think decidable is more commonly used for languages and sets but computable has the advantage of generalizing to functions. I have a slight preference for decidable. Pichpich (talk) 00:07, 21 February 2008 (UTC)
[edit] This needs a lot of work
I hadn't realized how sad the status of these articles were. For one thing, there's this insistence on viewing this in formal language terms which I suppose would make sense if we were in the 1960's. Maybe we should just have as a title Decidable sets and decision problems. The formal language point of view could be a small subsection noting the closure properties under concatenation and Kleene star. Nowadays, theoretical computer science textbooks have dropped the term formal language and simply talk about languages: the formal really made sense when Chomsky was studying this from a linguistic perspective. From a CS perspective, it's a useless prefix. Pichpich (talk) 00:35, 21 February 2008 (UTC)
- I think some of that is that the references people have were often written in the 1960s, or earlier; many of the original papers are accessible enough that people read them, although their terminology is out of date and their perspective limited.
- I started working on merging some things and smoothing over the edges. Here are a few particular thoughts:
- The lede probably doesn't need to stress over whether we have sets of natural numbers or sets of strings. This is at best a minor technical detail, and can be discussed in detail lower down. Why not simply say "set" in the lede, which I think it unlikely to confuse too many people.
- The stuff of Goedel's incompleteness theorem and its relationship to the halting problem doesn't belong here. It belongs either in the article on the halting problem or the article about Goedel's theorem. It's very tempting to mention Goedel's theorem in every possible article, but I think that temptation must be avoided. We could include a paragraph here, at most, if really desired, but the previous text was going too far afield from the topic at hand.
- I don't think the plan is to merge undecidable problem, right? Maybe I am confused.
- — Carl (CBM · talk) 01:28, 21 February 2008 (UTC)
I think there are a few good reasons to merge undecidable problem here also.
- Keeping them separate feels (to me) like having separate articles for continuous function and discontinuous function.
- No offense to the editors who wrote it but the undecidable problem article is in pretty bad shape. For one thing, there's all the Gödel incompleteness which, as you noted, is just irrelevant and in many ways misleading. There's also a whole section (which I did not cut and paste) about "undecidable statements" which is supposedly an alternate terminology for logically independent statements with respect to some theory. I've never seen that usage (and I don't think many logicians would like it). And of course, even if it is common terminology, it's on a different topic entirely and there should just be a see also pointing to Independence (mathematical logic).
- Take the undecidable problem article and remove a) the definition of decidable (which is covered in our new article), b) the Gödel discussion (which doesn't belong), c) the "undecidable statements" section (which doesn't belong) and d) the word-for-word cut and paste job from List of undecidable problems. What remains as useful content is the three-line section entitled The undecidable problem in Computability Theory, which in fact consists of the first three lines of the article Halting problem.
As for your comments on the lede, I have to agree with you. We should make it accessible and friendly at the risk of being somewhat informal. No need to scare away readers for the sake of mathematical precision, as long as we do get the details right in the main body. Pichpich (talk) 02:17, 21 February 2008 (UTC)
