No label defined (Q3755446)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4004170
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4004170 |
Statements
1985
0 references
effectively hyperimmune set
0 references
effectively immune set
0 references
partial recursive functions
0 references
0.9033263921737672
0 references
0.7948297262191772
0 references
0.7918019890785217
0 references
0.7875364422798157
0 references
Let f be a 1-1 recursive function. f is called strong table if (\(\forall x,y)(x\neq y\Rightarrow {\mathcal D}_{f(x)}\cap {\mathcal D}_{f(y)}=\emptyset)\), where \({\mathcal D}_ z\) denotes a finite set with canonical index z. An infinite set A is called an effectively hyperimmune set if there is a recursive function f such that \((\forall x)(\phi_ x\) is strong table \(\Rightarrow\) (\(\exists y\leq f(x))\) (\({\mathcal D}\phi_ x(y)\subset \bar A))\). An r.e. set A is effectively hypersimple if \(\bar A\) is effectively hyperimmune. In this paper the classes of effectively immune and effectively hyperimmune sets are investigated. Main results are the following theorems: 1. There is an effectively immune set whose Turing degree contains no hyperimmune sets. 2. Every effectively hyperimmune set is effectively immune. 3. Any r.e. set, when the direct enumeration of elements of its complement majorizes all partial recursive functions, is effectively hypersimple. 4. There exist r.e. sets whose complements majorize all partial recursive functions.
0 references