No label defined (Q3676134)

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 3896921
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3896921

      Statements

      0 references
      1982
      0 references
      limiting recursive functions
      0 references
      degree of unsolvability
      0 references
      Let f be a limiting recursive (l.r.) function, i.e., let there exist a two-place general recursive function g such that \(f(x)=\lim_{n\to \infty}g(n,x)\). If \[ (\forall x)(f(x)=\lim_{n\to \infty}g(n,x))\quad \&\quad (\forall x)(\forall m,n,k)(m<n<k\quad \&\quad g(m,x)\neq g(n,x)\quad \& \tag{1} \] \[ g(n,x)\neq g(k,x) \to g(m,x)\neq g(k,x)), \] then f will be called strictly l.r. If in addition to the restriction (1) we require that (\(\forall x)(\forall y)(x\neq y\to g(n,x)\neq g(m,y)\) for all m,n), then f will be called 1-1 \(\Pi\)-recursive (1-1 \(\Pi\)-r.). For sets A and B we will say that A 1-1 \(\Pi\)-reduces to B if there exists a 1-1 \(\Pi\)-r. function f such that (x\(\in A\leftrightarrow f(x)\in B)\). The author proves the following theorems: Theorem. A degree of unsolvability is r.e. if and only if it contains a strictly l.r. function. Theorem. A r.e. set with infinite complement is hypersimple if and only if it is not 1-1 \(\Pi\) reducible to its complement.
      0 references

      Identifiers