scientific article

zbMath0471.03003MaRDI QIDQ3924153

Yuri I. Manin

Publication date: 1980

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computabilityrandomnessGödel's theoremdiophantine setsrecursive groupscomplexity estimates for computations and algorithmsexistence of uncomputable functions and algorithmically undecidable problemsMatijasevic's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Decidability (number-theoretic aspects) (11U05) Undecidability and degrees of sets of sentences (03D35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Algorithms in computer science (68W99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (26)

From Monte Carlo to quantum computation ⋮ Milestone developments in quantum information and no-go theorems ⋮ Holographic software for quantum networks ⋮ Quantum circuits of $ \newcommand{\cZ}{c-\mathtt{Z}} \cZ$ and $ \newcommand{\Swap}{\mathtt{SWAP}} \Swap$ gates: optimization and entanglement ⋮ An exactly solvable quantum-metamaterial type model ⋮ Single qudit realization of the Deutsch algorithm using superconducting many-level quantum circuits ⋮ Pierced by a sun ray. An obituary of Yuri Ivanovich Manin (1937--2023) ⋮ Interference as a computational resource: a tutorial ⋮ Computers as a novel mathematical reality. I: A personal account ⋮ Quantum simulation of quantum mechanical system with spatial noncommutativity ⋮ Constructive simulation and topological design of protocols ⋮ Quantum walks for the determination of commutativity of finite dimensional algebras ⋮ Embedding of provably unsolvable problems into stream ciphers;Встраивание доказуемо неразрешимых задач в шифры гаммирования ⋮ On a poset of quantum exact promise problems ⋮ Quantum algorithms for learning hidden strings with applications to matroid problems ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ The Road to Quantum Computational Supremacy ⋮ Turbulence theories and statistical closure approaches ⋮ Information theories for time-dependent harmonic oscillator ⋮ The conjugacy problem for groups, and Higman embeddings ⋮ Introductive backgrounds to modern quantum mathematics with application to nonlinear dynamical systems ⋮ Bounding the costs of quantum simulation of many-body physics in real space ⋮ Biology as a constructive physics ⋮ On a Quantum Logical Element Associated with the Radical of a Complex Matrix ⋮ Entangling problem Hamiltonian for adiabatic quantum computation ⋮ Algorithm for initializing a generalized fermionic Gaussian state on a quantum computer

This page was built for publication: