Subrecursive hierarchies on Scott domains (Q688507): Difference between revisions

We study a suitable notion of partial primitive recursive (p.p.r.) function on the Scott domain \(D_ \iota=\{\perp,0,1,\dots\}\) of the natural numbers. A variety of subrecursive hierarchies with respect to p.p.r. is introduced and it turns out that they all coincide. A \(k\)-ary function \(f\) in the Scott domain \(D_ \sigma\) with \(\sigma:=(\underline\iota\to\iota)\) is said to be partial primitive recursive (p.p.r.) iff there exists a p.r. enumeration function \(A_ f\) of all finite approximations \(e^ \sigma_ n\) of \(f\), i.e. \(f\) is the least upper bound of all \(e^ \sigma_{A_ f(l)}\), and a p.r. bounding function \(B_ f\) such that \[ \forall\underline x\in\text{dom }f \exists l\leq B_ f(\lceil\underline x\rceil).\;\underline x\in\text{dom }e^ \sigma_{A_ f(l)}, \] where \(\text{dom }f\) denotes the domain of \(f\) and \(\lceil.\rceil\) a suitable coding function. Furthermore \(f\) belongs to the \(n\)-th extended Grzegorczyk class denoted \({\mathcal E}^*_ n\) iff \(A_ f\), \(B_ f\) above belong to \({\mathcal E}_ 3\), \({\mathcal E}_ n\), respectively, where \({\mathcal E}_ n\) denotes the \(n\)-th Grzegorczyk class. In Section 3 we define classes \({\mathcal L}^*_ n\) that we call the \(n\)- th Lifting class consisting of all computable functions which can be simulated on the codes of their arguments by a p.r. function in \({\mathcal E}_ n\), i.e. \(f(x)=\mathbf{if} f'(\lceil\underline x\rceil)>0\) \(\mathbf{then}\) \(f'(\lceil\underline x\rceil)-1\) \(\mathbf{else}\) \(\perp\) with \(f'\in{\mathcal E}_ n\). Then we prove \(\forall n\geq 3. {\mathcal E}^*_ n={\mathcal L}^*_ n\). Exploiting this characterization it is straightforward to prove the essential properties of the classes \({\mathcal E}^*_ n\). Especially it turns out that the Grzegorczyk classes \({\mathcal E}_ n\) can eventually be embedded in \({\mathcal E}^*_ n\) and represent therein exactly the total p.p.r. functions. Moreover the above hierarchy classifies all of the parallel computable functions provided they are p.p.r. With Section 4 we start a structural approach of classifying the p.p.r. functions. We define classes \({\mathcal R}^{*(F)}_ n\) of computable functions built from some simple initial functions by means of composition, a non-contextfree case definition scheme \((F)\) and at most \(n\) strict partial primitive recursions, and prove \(\forall n\geq 3. {\mathcal E}^*_{n+1}={\mathcal R}^{*(F)}_ n\). Section 5 deals with a merely syntactical version of \({\mathcal R}^{*(F)}_ n\) involving only contextfree schemes. Let \({\mathcal R}^{*(\ddot\mu)}_ n\) result from \({\mathcal R}^{*(F)}_ n\) by substituting the parallel conditional \(:\supset\) with the sequential one within the initial functions and a scheme of a parallel bounded parallel \(\mu\)-operator \((\ddot\mu)\) for \((F)\). Then we give a proof of \(\forall n\geq 3. {\mathcal E}^*_{n+1}={\mathcal R}^{*(\ddot\mu)}_ n\). Clearly it follows that the p.p.r. functions form the least class of computable functions containing the initial functions \(\lambda\underline x.0\), \(\lambda\underline x.x_ i\), \((+1)\), \((-1)\), \(:\supset\), and closed under composition, strict partial primitive recursion and \((\ddot\mu)\). Rounding off the theory, we present in section 6 an effective numbering \{.\} of the p.p.r. functions such that an \(S^ m_ n\) Theorem and Recursion Theorem hold with respect to \{.\}.