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
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
0.8293405771255493
0 references
0.8263039588928223
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