Subrecursive hierarchies on Scott domains
type: Item
instance of: scholarly article
title: Subrecursive hierarchies on Scott domains
zbMATH Open document ID: 0779.03011
DOI: 10.1007/BF01387405
author: Karl-Heinz Niggl
published in: Archive for Mathematical Logic
publication date: 1993-12-09T00:00:00Z
review text: 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 f…
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D75
zbMATH DE Number: 444894
zbMATH Keywords: partial primitive recursive function
zbMATH Keywords: Scott domain
zbMATH Keywords: variety of subrecursive hierarchies
zbMATH Keywords: extended Grzegorczyk class
zbMATH Keywords: Lifting class
zbMATH Keywords: parallel computable functions
zbMATH Keywords: parallel bounded parallel \(\mu\)-operator
zbMATH Keywords: effective numbering
MaRDI profile type: Publication
cites work: ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
cites work: Q5824357
cites work: LCF considered as a programming language
cites work: Classes of recursive functions based on Ackermann's function
cites work: Rekursionszahlen und die Grzegorczyk-Hierarchie
cites work: Q3959414
full work available at URL: https://doi.org/10.1007/bf01387405
OpenAlex ID: W2041255733
Recommended article: Q3695270
Recommended article: Q4876432
Recommended article: Recursive subhomogeneous algebras
Recommended article: A categorical generalization of Scott domains
Recommended article: On the congruence lattice of a Scott-domain
Recommended article: Recursion theorems and effective domains
Recommended article: A restricted computation model on Scott domains and its partial primitive recursive functionals
Recommended article: SCOTT COMPLEXITY OF COUNTABLE STRUCTURES
Recommended article: Q5295697
description: scientific article; zbMATH DE number 444894