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

      0 references
      1985
      0 references
      Skordev's conjecture
      0 references
      admissible function
      0 references
      search computable function
      0 references
      search computability
      0 references
      admissibility
      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

      Identifiers