Discrete families of recursive functions and index sets (Q1842381): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:40, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Discrete families of recursive functions and index sets |
scientific article |
Statements
Discrete families of recursive functions and index sets (English)
0 references
17 May 1995
0 references
Second order index sets of the discrete families of partial recursive functions (PRF) are studied. Let \(\{\varphi_e\}_{e \in \omega}\) be a Gödel numbering of the set of PRF. The \(e\)-th computable numbering is defined as follows: \(\nu^e : = \lambda i,x. \varphi_e (\langle i,x \rangle)\), and let \(\nu^e\) enumerate the family of PRF \(F^{(e)} : = \{ \lambda x. \nu^e (i,x)\}_{e \in \omega}\). Denote by \(I(F)\) the set \(\{e : F^{(e)} = F\}\), and denote by \(R_1\) the family of total recursive functions. The authors show: If \(A\) is a non-recursive recursively enumerable set then \(\{\langle i,j \rangle : W_i \cap W_j = \emptyset\;\&\;W_i \cup W_j = A \cap W_i\;\&\;W_i\) is nonrecursive\} is \(\Pi_3\)-complete. The family \(\{e : F^{(e)} \subseteq R_1\) is effectively discrete\} is \(\Sigma_3\)-complete. The family \(\{e : F^{(e)} \subseteq R_1\) is discrete\}, as well as the family \(\{e : F^{(e)} \subseteq R_1\) is discrete, but not effectively discrete\} are both \(\Pi_3\)-complete. The index set of any family \(F\) of total recursive functions which has exactly one (i.e. \(|L \{F\} |= 1)\) numbering up to numbering equivalence, is \(\Pi_4\)-complete. The article contains a series of other results closely related to the above-mentioned ones. A number of open problem are listed.
0 references
computable family
0 references
discrete class
0 references
semilattice
0 references
index sets
0 references
partial recursive functions
0 references
computable numbering
0 references
total recursive functions
0 references