Content deleted Content added
Zde~enwiki (talk | contribs) No edit summary |
→"if" versus "if and only if": explanation |
||
Line 15:
: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. [[User:Zde|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). --[[User:Trovatore|Trovatore]] 18:40, 3 January 2006 (UTC)
| |||