[:partial recursive:] • A function is partial recursive if it is primitive recursive, but we also include: • (unbounded search or μ\mu-recursion) for some partial recursive θ(x1,,xn,y)\theta(x_1, \dots, x_n, y), consider the partial function ψ(x1,,xn)\psi(x_1, \dots, x_n) giving the least yy where θ(x1,,xn,y)=0\theta(x_1, \dots, x_n, y) = 0 and each θ(x1,,xn,z)\theta(x_1, \dots, x_n, z) [converges](partial function) for each z<yz < y. Then ψ\psi is partial recursive. • Remark: we're basically adding the following •
javascript function psi(theta, ...xs) { for (let y = 0; true; y++) if (theta(...xs, y) === 0) return y; }
• Remark: while primitive recursive functions are all total, partial recursive functions may be partial functions • Remark: it seems that the set of partial recursive functions is of equal power to the set of turing machines; i.e., to say something is computable is to say that it is partial recursive • Another way of writing this is with the μ\mu quantifier, which is defined as follows: • μx:ϕ(x)\mu x : \phi(x) for some formula ϕ(x)\phi(x) is the least xN0x \in \mathbb N^{\geq 0} such that ϕ(x)\phi(x) holds • Then we can define ψ(x1,,xn,y)=μy:θ(x1,,xn,y)=0z<y:θ(x1,,xn)\psi(x_1, \dots, x_n, y) = \mu y : \theta(x_1, \dots, x_n, y) = 0 \land \forall z < y : \theta(x_1, \dots, x_n)\downarrow • Where \downarrow is used for [convergence](partial function) Referenced by: