×

zbMATH — the first resource for mathematics

Computability and numberings. (English) Zbl 1157.03022
Cooper, S. Barry (ed.) et al., New computational paradigms. Changing conceptions of what is computable. New York, NY: Springer (ISBN 978-0-387-36033-1/hbk). 19-34 (2008).
Let \(\alpha\) be a computable ordinal. Denote by \({\mathcal R}^0_\alpha({\mathcal A})\) the upper semilattice of \(\Sigma^0_\alpha\)-computable numberings of a family of \(\Sigma^0_\alpha\)-sets \(\mathcal A\). The authors prove that, if \(\alpha\) and \(\beta\) are computable ordinals, \(\alpha>0\), \(\alpha+3\leq\beta\), \(\mathcal A\) is a \(\Sigma^0_\alpha\)-computable family and \(\mathcal B\) is a non-trivial \(\Sigma^0_\beta\)-computable family then the Rogers semilattices \({\mathcal R}^0_\alpha({\mathcal A})\) and \({\mathcal R}^0_\beta({\mathcal B})\) are not isomorphic.
For the entire collection see [Zbl 1130.68005].

MSC:
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite