1
$\begingroup$

In the book Computability and Logic by Boolos, Burgess and Jeffrey (page 71 - 5th edition) it defines a recursive function as follows:

The functions that can be obtained from the basic functions $z, s, id^i_n$ by the processes $Cn, Pr$, and $Mn$ are called the recursive (total or partial) functions. (In the literature, ‘recursive function’ is often used to mean more specifically ‘recursive total function’, and ‘partial recursive function’ is then used to mean ‘recursive total or partial function’.)

The reason why I'm confused is because it seems to me that when the authors use the word 'recursive' when referring to functions built up from $z, s, id^i_n$ by the processes $Cn, Pr$, and $Mn$, it seems to allow that possibility that a partial function is also recursive (so we're not restricting the definition of recursive to just total functions). Is this the case in this book?

But then in page 93, there's a theorem that says that

A function is recursive if and only if it is Turing computable

So if I take my assumption on what 'recursive' means, it seems to me that they also allow partial functions to be turing computable. But based on what I've learnt and searching through the internet this doesn't seem to be the case? Or can recursive partial functions be Turing computable?

But a effectively computable partial function is not necessarily Turing computable right? Because if $n$ is not in the domain then we will never get an answer and so a Turing machine won't necessarily halt for that value of $n$.

On another note, I'm assuming recursive partial function is equivalent to a function being called semi-recursive? (I'm also not sure because semi-recursive relations were defined in the book, but not semi-recursive functions).

So what am I misunderstanding? Is my interpretation of 'recursive' in the book correct or am I mistaken?

Addendum: Unless what they mean by Turing-computable also includes Turing-recognizable? Maybe the confusion is that the word recursive as referred to functions include the partial cases whereas when referred to sets and relations they don't? So When you say a set is recursive, it doesn't include the semi-recursive case, unlike for functions. But I would like someone who actually has read the book to a sufficient amount to guarantee what the author really means.

$\endgroup$
2
$\begingroup$

The reason why I'm confused is because it seems to me that when the authors use the word 'recursive' when referring to functions built up from z,s,idin by the processes Cn,Pr, and Mn, it seems to allow that possibility that a partial function is also recursive (so we're not restricting the definition of recursive to just total functions). Is this the case in this book?

The authors say explicitly that they allow this possibility when they write "The functions [...] are called the recursive (total or partial) functions." The note that follows in parentheses is a warning that some other authors reserve the expression "recursive function" for total functions.

So if I take my assumption on what 'recursive' means, it seems to me that they also allow partial functions to be turing computable. But based on what I've learnt and searching through the internet this doesn't seem to be the case? Or can recursive partial functions be Turing computable?

A partial recursive function can absolutely be Turing-computable. (And the conditions are even equivalent.) For instance, see Theorem 5.3.10 in Logique Mathématique by Cori and Lascar, 2003:

Théorème. Toutes les fonctions récursives partielles sont $\mathrm{T}$-calculables.

The converse is stated in 5.3.14.

But a effectively computable partial function is not necessarily Turing computable right? Because if n is not in the domain then we will never get an answer and so a Turing machine won't necessarily halt for that value of n.

It is necessarily Turing-computable, by 5.3.10 above. If a Turing machine doesn't halt for a particular value of $n$, it can still be the case that that Turing machine computes a partial function, but that $n$ is not in the domain of that function.

On another note, I'm assuming recursive partial function is equivalent to a function being called semi-recursive?

I'm not sure what a semi-recursive function would be. You say they haven't defined it, and even if the concept existed, I wouldn't assume that it's what you're saying it is.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.