Content deleted Content added
→"if" versus "if and only if": explanation |
No edit summary |
||
Line 22:
::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)
== Circularity of Definitions ==
Isn't this [[Computable function#Definition|definition of a computable function]]:
A [[partial function]] <math>f:\subseteq \mathbb{N} \to \mathbb{N}</math>
is called '''computable''' if the [[graph of a function|graph]] of <math>f</math> is a [[recursively enumerable set]].
circular with the [[recursively enumerable set#Definition|definition of a recursively enumerable set]]:
A countable set S is called recursively enumerable if there exists a partial computable function <math>f : \mathbb{N} \to S</math> such that <math>S</math> is the range of <math>f</math>?
--[[User:Ashsong|Michael Stone]] 00:25, 11 March 2006 (UTC)
| |||