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
1982
0 references
limiting recursive functions
0 references
degree of unsolvability
0 references
0.741978108882904
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