Hi all,

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?

In article <b8922c23-8bee-469b-a1e3-7cf9aa934...@i29g2000prf.googlegroups.com>,

I think you're seeing a distinction here that was not intended.  The
statements that

  a relation is effectively decidable if its c.f. is effectively computable

and

  a relation is recursive if its c.f. is recursive

do not logically imply, and are not intended to suggest, that

  there exist relations that are effectively decidable but not recursive,
  and there exist relations that are recursive but not effectively decidable.

All that they're doing is giving some examples of the principle that when one
says that a relation is X, one means that its c.f. is X.  That does not mean
that two apparently different properties X and Y cannot coincide.
--
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

Thank you for your reply Tim. So do you agree with my opinion that
effectively decidable relation is the same thing as recursive
relation?

That's not what I thought, I just see only a terminological difference
between what they call effectively decidable relation and recursive
relation, because I think that relation is effectively decidable iff
it is recursive (ie. set's indicator function is effectively
computable iff it is recursive). And so mentioning these two terms in
that sentence seems little confusing to me.

In article <b71070ea-7025-468b-a4b2-3ed83e762...@y5g2000hsf.googlegroups.com>,

Yes, I believe that is correct, because as you mentioned, indicator functions
are always total.

Perhaps the parentheses around "primitive" weren't there originally and were
added as an afterthought.
--
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences

On 28 Lis, 16:00, tc...@lsa.umich.edu wrote:

Yes, that would make sense to me :) Thank you again Tim.