Definition talk:Recursive/Set

There are two senses of the word "recursive". There is primitive recursive, which is the linked definition, and then there is recursive in the sense of Turing ("computable" or "Turing computable"). In the latter case you would unravel the definition to "$B$ is recursive if and only if there is a Turing machine that accepts $n \in \N$ and outputs $1$ if $n \in B$ and $0$ otherwise". Every primitive recursive function is Turing computable, but the Ackermann function is Turing computable but not primitive recursive. For the sake of precision I would avoid the word "recursive", and instead say "(Turing) computable" and "primitive recursive". In the context of Godel's incompleteness theorem - we should definitely be talking about computability (which can be weakened to computable enumerability) in the sense of Turing. Caliburn (talk) 16:19, 22 May 2024 (UTC)

This page dates back from when I infodumped my Mathematical Logic course notes into $\mathsf{Pr} \infty \mathsf{fWiki}$ in one fell swoop, before we (that is to say, I) had even thought of backing up all definitions with hardcopy source works. As and when you find what these definitions are actually referred to by name, feel free to rename them as appropriate.

I have added a "no sources" template to this page (and related ones) because this is as you suggest unreliable. --prime mover (talk) 17:30, 22 May 2024 (UTC)