Talk:Computably enumerable set

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)

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

"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).[reply]

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)[reply]

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)[reply]