Computability (Q3751553)

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

      Statements

      0 references
      1987
      0 references
      recursive sets
      0 references
      partial recursive functions
      0 references
      recursively enumerable sets
      0 references
      Church's thesis
      0 references
      unsolvable problems
      0 references
      numberings
      0 references
      productivity
      0 references
      reducibilities
      0 references
      computational complexity
      0 references
      Kleene hierarchy
      0 references
      recursion theorem
      0 references
      type 2 theory of constructivity and computability
      0 references
      theory of representations
      0 references
      semantics
      0 references
      recursion analysis
      0 references
      Computability (English)
      0 references
      The book deals with ''the pure theory of computability'' which is the common basis for all subdomains of recursion theory: it is divided into three parts, gradually leading from basic theory to modern concepts of computability. Part I (undergraduate level) introduces basic properties of computability on natural numbers and on words (some concepts: computability models, recursive and recursively enumerable sets, partial recursive number functions, Church's thesis, unsolvable problems). Part II contains standard recursion theory (some concepts: numberings, productivity, reducibilities, computational complexity, Kleene hierarchy, recursion theorem. Part III (which can serve as a monograph for experts) presents a unified and systematic type 2 theory of constructivity and computability (i.e. computability on sets with the cardinality of the continuum) which has no previous model in the literature: this part deals mainly with basic type 2 theory of constructivity and computability on Baire space, general theory of representations, and with important applications of the results to semantics and to recursion analysis.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references