From here: what about ? Do we need it?


I propose to create the synonym

The terms may come from different schools, but as far as I know, describe the same field. In particular, a function is recursive (in the sense of this theory) if and only if it is computable.

FWIW, Wikipedia does not seem to separate the terms.

(We may want to go for consistency, but well.)

  • $\begingroup$ But I think the point is that they do come from different schools. A question about Turing machines is unlikely to be interesting to somebody who studies computability via mathematical functions, and vice-versa. Is there any particular need to merge the two? $\endgroup$ – David Richerby Aug 31 '16 at 14:28
  • $\begingroup$ @DavidRicherby We "have" to have one tag for the whole field. If these two terms describe the same thing, the are, quite litearally, synonyms. We have turing-machines, lambda-calculus, and we could have mu-recursion or admissible-numberings (sadly, there are few questions about that; before removing recursion-theory I would go and add recurision-theory-lingo tags where necessary.) That should be enough to focus questions more if necessary? $\endgroup$ – Raphael Mod Aug 31 '16 at 15:21
  • $\begingroup$ @DavidRicherby If somebody asks about computability in general, e.g. "how do I show that problem X is (un)decidable?", I don't think answers using, say, µ-recursion or admissible numberings would be offtopic. $\endgroup$ – Raphael Mod Aug 31 '16 at 15:22
  • 1
    $\begingroup$ I think my point is that I feel that recursion-theory is a strict subset of computability, so I don't feel that they're synonyms. I don't think synonymizing them would be terrible but I don't see any advantage in doing it. $\endgroup$ – David Richerby Aug 31 '16 at 15:28
  • $\begingroup$ If you have evidence of the strictness, I'm all ears. The advantage would be to get rid of a rarely used tag whose use may leave computability questions without that tag and hence harder to find. (E.g. if users have been taught by somebody in that school and use the term recursion theory as opposed to computability theory.) $\endgroup$ – Raphael Mod Aug 31 '16 at 21:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .