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 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

      Identifiers