Talk:Recursive set

From Wikipedia, the free encyclopedia

[edit] Reverse redirect

Right now, Computable set redirects to recursive set. Are there any objections if I reverse that redirect? CMummert 23:35, 16 July 2006 (UTC)

[edit] Hierarchy error

The article says that a set is recursive if and only if it is at level \Delta_1^0 of the arithmetical hierarchy. That means it is definable by a formula beginning with an unbounded quantifier and using only bounded quantifiers thereafter. This doesn't seem too likely. For instance, one \Delta_1^0 set is the set of numbers which are bounded above by a twin prime, which is not known to be recursive AFAIK. I certainly can't think of a good algorithm for determining that :-) Luqui 11:49, 8 July 2007 (UTC)

Pardon me, I have made an error. My twin primes statement is \Pi_1^0 but probably not \Sigma_1^0, so it's not \Delta_1^0. Luqui 11:54, 8 July 2007 (UTC)
You are confused about something. The "set of numbers which are bounded above by a twin prime" is either:
  • The entire set of natural numbers, if there are infinitely many twin primes
  • or a set of the form {0,1,2,...,p,p+1} where p and p+2 are the largest pair of twin primes.
Therefore (proof by cases) this is a recursive set, although it isn't known which of these sets it is. — Carl (CBM · talk) 13:05, 8 July 2007 (UTC)

[edit] 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:42, 21 February 2008 (UTC)

Oppose merger A lot of effort has gone into perfecting Recursively enumerable set. I do not want it to be destroyed by merging it into another, inferior article. JRSpriggs (talk) 01:33, 27 May 2008 (UTC)