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, Bounding the costs of quantum simulation of many-body physics in real space, On a Quantum Logical Element Associated with the Radical of a Complex Matrix, Single qudit realization of the Deutsch algorithm using superconducting many-level quantum circuits, Information theories for time-dependent harmonic oscillator, Comparative complexity of quantum and classical OBDDs for total and partial functions, Introductive backgrounds to modern quantum mathematics with application to nonlinear dynamical systems, Holographic software for quantum networks, From Monte Carlo to quantum computation, Turbulence theories and statistical closure approaches, Biology as a constructive physics, Quantum walks for the determination of commutativity of finite dimensional algebras, The Road to Quantum Computational Supremacy