No label defined (Q3705441)
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 3930992
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3930992 |
Statements
1985
0 references
Skordev's conjecture
0 references
admissible function
0 references
search computable function
0 references
search computability
0 references
admissibility
0 references
0 references
0.8223491
0 references
0 references
0 references
B. Skordev has conjectured that search computability over a countable domain B is equivalent to admissibility, where \(\phi: B^ n\to B\) is admissible in given functions \(\psi_ 1,...,\psi_ l\) and predicates \(P_ 1,...,P_ m\) over B iff for all enumerations \(\alpha\) of B it has a partial recursive associate (i.e. function f s.t. \(\phi (\alpha (i_ 1),...,\alpha (i_ n))\simeq \alpha (f(i_ 1,...,i_ n)))\), provided \(\psi_ 1,...,\psi_ l\) and the semi-characteristic functions of \(P_ 1,...,P_ m\) do so. The author has shown earlier [Serdica 7, 117-130 (1981; Zbl 0497.03034)] that search computability implies admissibility. This paper establishes the converse under the assumption that \(\psi_ 1,...,\psi_ l\) are total and \(m=0.\) It is worth mentioning that, as proved by I. Soskov, search computability equals prime computability and equals term expressibility in such a case, hence this result can be reformulated as follows: the functions admissible in total \(\psi_ 1,...,\psi_ l\) are exactly those which can be obtained from \(\psi_ 1,...,\psi_ l\) by superpositions. In general Skordev's conjecture has been refused by Soskov's observation that there exist partial functions \(\psi_ 1,...,\psi_ l\) which have no partial recursive associates. In view of this the author has proposed that a function be called admissible in \(\psi_ 1,...,\psi_ l\), \(P_ 1,...,P_ m\) iff for all enumerations it has an associate partial recursive in associates of \(\psi_ 1,...,\psi_ l\) and the characteristic functions of \(P_ 1,...,P_ m\); his results hold for this modified notion as well.
0 references