×

\({\mathcal F}\)-computable numbers. (English) Zbl 0537.68044

Let \({\mathcal F}\) be a set of functions with arguments and values in the set of natural numbers. The authors introduce the sets \(N_ 1({\mathcal F})\), \(N^ k({\mathcal F}) (k>1)\) and \(N_ 3({\mathcal F})\) of computable numbers and they study the properties of those sets in the following cases: (1) \({\mathcal F}\) is an elementary class; (2) \({\mathcal F}={\mathcal P}({\mathcal N}{\mathcal P})\), where \({\mathcal P}({\mathcal N}{\mathcal P})\) is the set of all functions computable by deterministic (nondeterministic) Turing machines in polynomial time; (3) \({\mathcal F}=EXP\), where EXP is the set of all functions computable by Turing machines in superexponential time.

MSC:

03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDFBibTeX XMLCite