Discrete families of recursive functions and index sets (Q1842381): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4168603 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theorie der Numerierungen I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inductive Inference and Computable One‐One Numberings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A STRUCTURAL CRITERION FOR RECURSIVE ENUMERATION WITHOUT REPETITION / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hyperarithmetical Index Sets in Recursion Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Family of all Recursively Enumerable Classes of Finite Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4063428 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198743 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4168913 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819052 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220577 / rank | |||
Normal rank |
Revision as of 13:07, 23 May 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