Publication:3924153

zbMath0471.03003MaRDI QIDQ3924153

Yuri I. Manin

Publication date: 1980

zbMATH Keywords

computability; randomness; Gödel's theorem; diophantine sets; recursive groups; complexity estimates for computations and algorithms; existence of uncomputable functions and algorithmically undecidable problems; Matijasevic's theorem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

11U05: Decidability (number-theoretic aspects)

03D35: Undecidability and degrees of sets of sentences

03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D25: Recursively (computably) enumerable sets and degrees

68W99: Algorithms in computer science

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

The conjugacy problem for groups, and Higman embeddings, Information theories for time-dependent harmonic oscillator, Introductive backgrounds to modern quantum mathematics with application to nonlinear dynamical systems, From Monte Carlo to quantum computation