What is the best redirect target?
Apparently, this warrants discussion.
D.Lazard insists that this page should redirect to Undecidable problem with the following reasoning: "except for logicians, semi-decidable refers to problems, not to sets. In any case, undecidable problem links to recursively enumerable set and better explains the relation between problems and sets". I disagree on several counts.
- Computability theory is inherently a formal topic that should be dealt with mathematically/logically. Any trivialisation introduces only confusion, as can often be observed by the questions people ask on Computer Science Stack Exchange. Therefore, the prefix "except for logicians" (intended to be derogatory?) is not only meaningless, but actively harmful in the context of deciding how to best represent TCS topics on Wikipedia.
- In the realm of TCS, (decision) problems are languages. There is no meaningful difference. The sad fact that Wikipedia has TCS terminology mixed and mangled does not change that.
- Redirecting to Undecidable problem suggests that semi-decidability and decidability are the same thing, which they are not.
- Recursively enumerable sets are computationally equivalent to semi-decidabile problems, so it's the proper redirection target.
- If there is explanation on Undecidable problem that would help on Recursively enumerable set, then it should be copied or linked there.
In summary, I maintain that the current redirection is bad and should be changed. Or, you know, a dedicated article linking in an explanatory way to the related concepts could be created. — Preceding unsigned comment added by contribs) (talk • contribs) 10:55, 1 February 2016 Akerbos (talk
- Please sign posts in talk page with four tildes (~~~~). D.Lazard (talk) 11:27, 1 February 2016 (UTC)
- One must keep in mind that Wikipedia is an encyclopedia, and as such, its target audience is the general public, not the experimented mathematicians who are mainly interested with formal rigor. In this case, the redirect exists for people who encounter somewhere the word "semi-decidable", and want to understand it. It is highly probable that most such people encounter this word in the context of algorithms (semi-algorithms) and practical computability, and thus that they do not know about recursively enumerable sets. Moreover, even if they know about calculability theory, it is also probable that, in most case, it has been presented to them in terms of Türing machines or RAM abstract machines, as these theories, although formally equivalent to recursivity allow a more natural definition of complexity. Therefore, the redirect has to be done toward the less WP:technical target.
- Another reason is that "semi-decidable problem" is a WP:primay topic for semi-decidability. In fact, if recursively enumerable sets are also called semi-decidable sets, this is because it is a formalization (one among several) of the intuitive notion of semi-decidable problem. Again, this is not the the formalization that interest most readers, but the intuitive notion, and, maybe, the fact that it may be formalized.
- IMO, "semi-decidable" would deserve to be a true article. Are you willing to wire it? Nevertheless, it is a pity that in most articles about decidability, the other formalizations of the concept (and especially Türing machines) are not even mentioned. D.Lazard (talk) 12:21, 1 February 2016 (UTC)
D.Lazard (talk) 12:21, 1 February 2016 (UTC)
- I don't understand what distinction is being made here. Decision problems (as specifications of which inputs should have the answer yes and which no), languages (sets of strings, the strings for which the answer should be yes), and sets (maybe of natural numbers rather than strings) are all equivalent formalizations of the same concept. Why do we have three different link targets, none of which clearly state that these are all equivalent ways of thinking about the same thing? —David Eppstein (talk) 01:14, 16 February 2026 (UTC)
- This discussion was started at Wikipedia:Redirects for discussion/Log/2026 February 15#Semi-decidable. Both of the following solutions seem reasonable to me:
- Create a disambiguation page (at Semidecidability or Semidecidable) that links to Decidability (logic)#Semidecidability, Recursively enumerable language and Computably enumerable set (but no other pages; Undecidable problem isn't appropriate)
- Create a new article Semidecidability about the general concept, with sections about (and links to) the three variants (or are there more?)
- Or maybe create the disambiguation page now (only takes a few minutes) and convert it to an article later... But I'm far from an expert in this area. I hope it's ok if I ping a few users who seem to be around and have contributed to these or related articles: @D.Lazard @Jochen Burghardt: What do you think? (I bet there are many others, but I'm not very active in that area...) — Chrisahn (talk) 03:08, 20 February 2026 (UTC)
- This discussion was started at Wikipedia:Redirects for discussion/Log/2026 February 15#Semi-decidable. Both of the following solutions seem reasonable to me: