Talk:Computable set

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)

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)

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)

Oppose and remove template My reasons are quite independent of the current state of the article. The fact is that r.e. sets can be significantly more complex than recursive ones, and there's quite a lot to say about them. Since this proposal has attracted no support in more than five months, I'm removing the template. --Trovatore (talk) 02:38, 9 August 2008 (UTC)

Power sets of the empty set

Are these "recursive sets", as claimed here?

Hi. Some time ago the interesting set P^4({}) = P( P( P(P({})))) has been used in the logical connectives article, but was removed.

Originally this came from Commons user Dohduhdah and his homepage. Where ever he's got this from, he doesn't remember.

In the description of his diagram File:Set0.gif (hard to read, but equal to my Hasse diagram on the right) he calls this "recursive sets". Does it make sense?

Thanks, Watchduck (talk) 13:17, 12 June 2009 (UTC)

I think he is confusing recursive sets with pure sets. JRSpriggs (talk) 21:08, 12 June 2009 (UTC)

Possibly, as they are pure for sure. But I should mention, that there is a bijection between these sets and natural numbers. On the right, you see the first sixteen sets between {} = 0 and { {} , {{}}, {{{}}} , {{},{{}}} } = 15. The next set would be {{{{{}}}}} = 16, and so on. Maybe it's helpful to know that, to decide if they are both pure and recursive. Watchduck (talk) 11:01, 13 June 2009 (UTC)

Diagram Misleading

Diagram showing the closure of decision problems in computational theory.

The diagram at the top of the page is misleading: decidable sets are a subset of recursively enumerable sets, but not of undecidable sets. —Preceding unsigned comment added by 78.131.31.31 (talk) 18:38, 9 November 2009 (UTC)

You are right; the diagram should be different. I moved it here so people can still see what you are referring to. — Carl (CBM · talk) 18:53, 9 November 2009 (UTC)

Gödel numbers

VladimirReshetnikov (talk · contribs) has twice added to Recursive set#Formal definition a paragraph saying that Gödel numbers can be used to extend the definition of recursive to sets which are not subsets of the natural numbers. If no restriction is imposed on how the Gödel numbers are formed, this is false and would make every countable set recursive. Suppose A is any countably infinite set (of course all finite sets are recursive) and in particular the function f is a bijection between the natural numbers and A. For each element a of A, let us declare the Gödel number of a to be the natural number n such that f(n)=a. Then A is the subset of itself corresponding to the recursive set N (all the natural numbers), and thus would be recursive by this extension of the definition.
Since this extension of the definition would reduce it to a triviality, I will revert it. JRSpriggs (talk) 21:00, 11 December 2011 (UTC)

Yes, I think you did the right thing. I think I understand Vladimir's point — it's not uncommon to speak of recursive or r.e. sets of this or that sort of thing other than natural numbers, when the things are naturally coded as natural numbers. But I don't know that there's a way generalize this observation and put it into the articles, without running into the problem you identify. In any case it would need a source. --Trovatore (talk) 21:18, 11 December 2011 (UTC)

Indeed, without restrictions on encoding it can lead to a wrong conclusion. I will look for sources explaining how to handle this. VladimirReshetnikov (talk) 19:45, 12 December 2011 (UTC)

To Vladimir: Thanks. It would be nice to find a restriction which would allow us to include this extension. Essentially the Gödel numbering itself needs to be recursive or, better, primitive recursive. Notice that the generalized notion of recursive must be closed under composition, and the same as the usual notion when restricted to the natural numbers. JRSpriggs (talk) 06:43, 14 December 2011 (UTC)

What would it mean for an algorithm on an arbitrary countable set to be recursive? I don't see a general definition of that which does not assume the prior existence of a numbering. It could be defined on a case by case basis for many of the countable sets which we encounter in practice, because they have nice numberings, of course.

One other way is to use the Weirauch-style definitions. Unfortunately we don't seem to have any article on what they call type two computability. The idea is that the numbering is just an arbitrary partial sujection from $\mathbb {N}$ or $\mathbb {N} ^{\mathbb {N} }$ to the set X; if δ(z) = y then z is a "name" for y. A function $g$ is δ-computable if there is an algorithm that, given a name for an element y, produces a name for g(y). The function δ is just a function, it has no effectiveness requirements. So the definition of δ-computability does depend on δ, but one nice aspect of it is that the definition is quite general. — Carl (CBM · talk) 12:47, 14 December 2011 (UTC)

To CBM: Are you saying that we could have a notion of recursive relative to an oracle with the Gödel numbering provided by the oracle? See Oracle machine. Although that is still limited to subsets of the natural numbers, perhaps one could encode some sets (beyond V_ω) as natural numbers. Maybe using infinitary logic?

I was thinking more along the lines of trying to extend the domain from the natural numbers to the constructible sets or perhaps just the ordinal numbers. JRSpriggs (talk) 11:04, 15 December 2011 (UTC)

Boolean algebra of recursive sets

Because the empty set and the set of natural numbers are recursive sets, and because recursive sets are closed under intersections, unions, and complements, they form a boolean algebra. Computably enumerable sets are closed under intersections and unions but not under complements and thus form a (bounded) distributive lattice. These are fun facts, but I don't know if they are of any use at all (I am by no means an expert in computability theory). If these facts are useful then I suggest that they be added to this article as well the article 'recursively enumerable set', and even if they are totally useless, perhaps they are interesting enough to be included anyway. Let me know what you think. Joel Brennan (talk) 20:50, 16 May 2019 (UTC)

Sounds like a good idea to me, if you include a reference. JRSpriggs (talk) 09:09, 17 May 2019 (UTC)