Question about indicator function of recursive and r.e. sets
- From: Twoflower <standa.kurik@xxxxxxxxx>
- Date: Tue, 27 Nov 2007 12:16:18 -0800 (PST)
at our lecture from Theory of Computation, we've been told that
- the set M is recursive, if its indicator function is total recursive
function (or partial recursive function, it doesn't make a difference
here, since indicator function is always EVERYWHERE defined).
Ok, I thought I understood this. But today, I found this quotation
from some book on Wikipedia:
"The characteristic function of a k-place relation is the k-argument
function that takes the value 1 for a k-tuple if the relation holds of
the k-tuple, and the value 0 if it does not; and a relation is
effectively decidable if its characteristic function is effectively
computable, and is (primitive) recursive if its characteristic
function is (primitive) recursive."
What I don't get here is the difference between "effectively decidable
relation" and "recursive relation". In the first case, they say the
characteristic function has to be effectively computable (ie. partial
recursive, if I'm not mistaken). In the second case the characteristic
function has to be recursive (it's what we call total recursive
function, am I right?). But on the lecture we've been told there is no
difference between these two cases...I'm little confused.
Could someone please enlighten this to me, please?
- Prev by Date: Re: Why isn't NP simply "not polynomial"?
- Next by Date: Re: Question about indicator function of recursive and r.e. sets
- Previous by thread: Call for Papers - 13th IEEE Workshop on Dependable Parallel, Distributed and Network-Centric Systems (DPDNS08)
- Next by thread: Re: Question about indicator function of recursive and r.e. sets