Talk:Recursively enumerable set

From Wikipedia, the free encyclopedia

Contents

[edit] Tuple

What the hell is a tuple??

An ordered pair. Dysprosia 03:23, 12 Dec 2003 (UTC)


No: All ordered pairs are tuples, but many tuples are not ordered pairs; some are ordered triples, etc. Michael Hardy 21:10, 12 Feb 2004 (UTC)

Ehm.. Tuple --NavarroJ 12:59, 20 August 2007 (UTC)

[edit] Is this correct?

"There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if it is a member of S and otherwise runs forever." I've changed this sentence because all recursive sets are also recursively enumerable. Algorithms for RE sets are simply not guaranteed to halt if the input is not a member of the set. Also notice that the above sentence contradicts one of the examples.

Both versions are correct. But perhaps your version is clearer. If I have an algorithm A for a recursive set S which terminates if an element e is not in S I can create a new algorithm A' which is the same as A but instead of terminating if e is not in S it goes into an infinite loop. Using this construction I can covert all terminating algorithms into non-terminating ones.
P.S.If you post messages on talk pages please sign your message with ~~~~.MathMartin 19:19, 5 Apr 2005 (UTC)
Actually, Matiyasevich's Theorem says the converse: Every recursively enumerable set is Diophantine. Jim

[edit] "if" versus "if and only if"

I can not agree with the wording "... eventually halts if and only if the input is an element of S ...". If it was so, recursive set could not be recursively enumerable, as the algurithm stops for input not being from S. I have changed the wording to "... eventually halts if the input is an element of S ...". This will allow recursive sets being also recursively enumerable. Zde 15:09, 3 January 2006 (UTC).
Unfortunately your definition allows any set whatsoever to be recursively enumerable. (Think about it.)
Given a recursive set, it's true that there's an algorithm that always halts and says whether the input is or is not in the set. But there's another algorithm that halts if and only if the input is in the set. For example, take your first algorithm, and rewrite it so that whenever it would have halted saying the element is not in the set, it instead goes into an infinite loop. (This is actually how you prove that recursive sets are recursively enumerable, or one way to prove it anyway.)
Accordingly, I'm reverting your edit (don't take it personally; it's a simple matter of correctness). --Trovatore 18:40, 3 January 2006 (UTC)

[edit] Circularity of Definitions

Isn't this definition of a computable function:

A partial function f:\subseteq \mathbb{N} \to \mathbb{N} is called computable if the graph of f is a recursively enumerable set.

circular with the definition of a recursively enumerable set:

A countable set S is called recursively enumerable if there exists a partial computable function f : \mathbb{N} \to S such that S is the range of f? --Michael Stone 00:25, 11 March 2006 (UTC)

Good catch. The definitions in computable function should be reworked, and probably computable function and recursive function should be merged. --Trovatore 00:41, 11 March 2006 (UTC)

[edit] Invalid definition of r.e. set

This is the invalid definition of recursively enumerable set from the article

There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if and only if the input is an element of S.

The problem is that there is no formal definition of algorithm (unless you choose the nonstandard definition that identifies algorithms with Turing machines, or something else equally nonstandard). The definitions of recursively enumerable set that apear in current texts all make reference to one of the several equivalent formally defined models of computation. It is only via Church's thesis that they identify the sets that are recursively enumerable with the sets that are enumerable by some “algorithm.” This confusion about Church's thesis is pervasive in many of the articles about computability.

Several of the comments for the suggested merge of Recursive function and Computable function suffer from the same confusion. There can be no formal definition of computable function which does not make reference to some model of computation.

CMummert 20:25, 14 July 2006 (UTC)

[edit] Equivalent definitions?

I can't see how both definitions can be considered "equivalent". I can see how, having an algorithm that enumerates the set, I can have another algorithm that, given an input number, eventually halts iff the element is in the set. But I can't see how, having such an algorithm, I could possibly enumerate the elements of the set. -- Anonymous, 13:20, 23 August 2006 (UTC)

The definitions aren't considered equivalent -- they are provably equivalent. If you have an algorithm A that halts on exactly those numbers that are in a set S, you can enumerate S based on how many steps it takes A to halt, as follows. Run A for one time step on input 0. Then run A for two time steps on input 0 and for two time steps on input 1. Then run A for three time steps on each of the inputs 0, 1, and 2. Whenever you run A long enough on a particular input that A halts, enumerate that input into S. If you continue methodically in the pattern just listed, you run A arbitrarily long on every input, and thus your enumeration will include every number for which A halts. CMummert 13:53, 23 August 2006 (UTC)

[edit] Does S have to be a set of natural numbers?

Why not just say that a set S (of natural numbers, teacups, or whatever) is r.e. if <insert favored def. here>? Why (as is done in the article) restrict S to a set of nat. num's and attempt to accommodate other sets via goedel numbering? Infinite sets of natural numbers don't necessarily have godel numbers. Consider the set C of those that do. Now consider one that doesn't--of course, it's not possible to actually specify one--and call it s. C U {s} is r.e., but not (not entirely) due to goedel numbering. In any case, it seems to me that the best method would be to present the general definition (where the nature of the elements of S is left unspecified) and then later, if necessary, restrict attention to r.e. sets of natural numbers. ...or more simply: C U {teacup} is r.e., but goedel numbering won't tell which is the x s.t. f(x) = teacup —The preceding unsigned comment was added by Futonchild (talk • contribs) 06:25, 28 February 2007 (UTC).

The problem is that there is no definition of an r.e. set of teacups, because no computer has ever been seen to output a teacup. CMummert · talk 13:14, 28 February 2007 (UTC)
No computer has ever been seen to output a natural number, either. But the set of natural numbers is r.e. all the same. --Futonchild 17:04, 28 February 2007 (UTC)
What exactly do you believe is the formal definition of "the set A is recursively enumerable"? CMummert · talk 18:43, 28 February 2007 (UTC)
You are right. The range of a recursive function has to be a set of natural numbers, so an r.e. set has to be a set of nat num's too. This makes me think though that maybe the comment about goedel numberings should be edited to reflect the fact that a goedel numbering function, while clearly intuitively effectively computable, cannot be, strictly speaking, recursive--? Also, does this mean that the Church-Turing thesis must also be restricted to functions from (n-tuples of) nat. num's to nat. num's--since clearly there are effectively computable functions (e.g. goedel numberings) that are not recursive? --Futonchild 21:52, 28 February 2007 (UTC)
Yes, it is true that the things called Godel numberings in computability theory, like the Godel numbering of the sentences of a formal language, cannot literally be "computable functions" unless their domain and range are included in the set of legal inputs/outputs of whatever model of computation we use. I used the word "corresponds" in this article precisely for that reason. Unfortunately the WP article on Godel numberings is currently in very bad shape. Feel free to edit either article if you would like to improve them.
And yes, the Church-Turing thesis is limited to functions whose domain and range are included in the set of possible inputs/outputs of the model of computation. For example, the successor operation on ordinals, although in some sense effective, can't be computable because there is no model of computation that can represent all the ordinals as inputs. CMummert · talk 23:14, 28 February 2007 (UTC)