scientific article

Publication date: 23 January 1993

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

primality exponentiation exercises diophantine complexity bounded universal quantifiers diophantine coding Four-Color Problem implications of negative solution to Hilbert's tenth problem recursive unsolvability of Hilbert's Tenth Problem universal diophantine equations

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Decidability and field theory (12L05) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Decidability of theories and sets of sentences (03B25) Diophantine equations (11D99)

Related Items

Counting Restricted Partitions of Integers into Fractions: Symmetry and Modes of the Generating Function and a Connection to $\omega(t)$, Short Presburger Arithmetic Is Hard, Unsolvability of some problems about piecewise-polynomial functions, Hypergeometric structures in Feynman integrals, Incompleteness of arithmetic from the viewpoint of Diophantine set theory, On polynomial-modular recursive sequences, On the existential arithmetics with addition and bitwise minimum, On some algebraic ways to calculate zeros of the Riemann zeta function, What's decidable about discrete linear dynamical systems?, The Riemann hypothesis as the parity of special binomial coefficients, Exponential diophantine equations in rings of positive characteristic, Conservative expansions of substructural logics, THE EXPONENTIAL DIOPHANTINE PROBLEM FOR, Solving equation systems in ω-categorical algebras, The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem, The concept of truth in a finite universe, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, The computational complexity of some problems of linear algebra, Unnamed Item, Preface, Polynomially Ambiguous Probabilistic Automata on Restricted Languages, REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS, Rational subsets of unitriangular groups, Unnamed Item, Unnamed Item, Unnamed Item, Model Theory in Algebra, Analysis and Arithmetic: A Preface, On the solvability of a class of Diophantine equations and applications, A direct method for simulating partial recursive functions by Diophantine equations, Polynomially ambiguous probabilistic automata on restricted languages, Learning power and language expressiveness., On computational complexity of graph inference from counting, Numerical solution of certain exponential and non-linear Diophantine systems of equations by using a discrete particle swarm optimization algorithm, Undecidability through Fourier series, Transformations of normal and inverted function tables, Further results on Hilbert's tenth problem, Optimization modulo non-linear arithmetic via incremental linearization, On two-way FA with monotonic counters and quadratic Diophantine equations, On the complexity of decision using destinies in $H$-bounded structures, The computability, definability, and proof theory of Artinian rings, Graph compression and the zeros of polynomials, The undecidability of proof search when equality is a logical connective, On checking existence of infinitely differentiable solutions of partial differential equations with boundary conditions, Affine linear sieve, expanders, and sum-product, Mechanically proving termination using polynomial interpretations, Is complexity a source of incompleteness?, On the expressiveness and decidability of o-minimal hybrid systems, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, Finding all solutions of equations in free groups and monoids with involution, Hilbert's problems and their sequels, Diophantine representations of linear recurrences. I, More Than 1700 Years of Word Equations, Representation theorems for recursively enumerable sets and a conjecture related to Poonen's large subring of $\mathbb Q$, Towards finite-fold Diophantine representations, The quest for Diophantine finite-fold-ness, A transfer method from bounded existential Diophantine equations to Tarski algebra formulas, Existential Diophantine definability of string length, Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable, Semiautomatic structures, Solving Nonlinear Integer Arithmetic with MCSAT, Diophantine hierarchy, Extending and interpreting Post's programme, Recursive analysis of singular ordinary differential equations, On a theorem of Matiyasevich, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, On an undecidable problem related to difference equations with parameters, Solving word equations modulo partial commutations, Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation, On testing the existence of universal denominators for partial differential and difference equations, Macsyma: A personal history, Inferring answers to queries, Products of matrices and recursively enumerable sets, Hypercomputation with quantum adiabatic processes, Hypercomputation by definition, The de Jongh property for basic arithmetic, $S_{k,\text{exp}}$ does not prove $\text{NP} = \text{co-NP}$ uniformly, Diophantine representations of linear recurrent sequences. II, A switch convergence for a small perturbation of a linear recurrence equation, Uncomputably large integral points on algebraic plane curves?, Martin Davis’s Bibliography 1950–2015, Quasi-universal $k$-regular sequences, From Mathesis Universalis to Provability, Computability, and Constructivity, Generalizing Riemann: from the L -functions to the Birch/Swinnerton-Dyer conjecture, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, The fixed point problem of a simple reversible language, On nonlinear multi-covering problems, Quantum revivals of a non-Rabi type in a Jaynes-Cummings model, Knapsack problem for nilpotent groups, Notes on the computational aspects of Kripke's theory of truth, Computational completeness of equations over sets of natural numbers, On a Diophantine representation of the predicate of provability, The scope of Gödel's first incompleteness theorem, Analytic methods in quantum computing, Economic Dynamics and Computation—Resurrecting the Icarus Tradition, On two-way nondeterministic finite automata with one reversal-bounded counter, On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases, On rational solutions of linear partial differential or difference equations, Checking existence of solutions of partial differential equations in the fields of Laurent series, The case for hypercomputation, Embedding infinitely parallel computation in Newtonian kinematics, Church's thesis meets the $N$-body problem, On deciding stability of multiclass queueing networks under buffer priority scheduling policies, MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM, Quantum principles and mathematical computability, Freeness properties of weighted and probabilistic automata over bounded languages, On the algorithmic undecidability of the embeddability problem for algebraic varieties over a field of characteristic zero, Some specially formulated axiomizations for $\mathrm{I}\Sigma _0$ manage to evade the Herbrandized version of the second incompleteness theorem, Finding numerical solutions of Diophantine equations using ant colony optimization, The computational status of physics, On pseudo algebraically closed extensions of fields, Existential arithmetization of Diophantine equations, What can and cannot be done with Diophantine problems, The Invariance Problem for Matrix Semigroups, Infiniteness sets of primes, admitting diophantine representations in eight variables, A new technique for obtaining diophantine representations via elimination of bounded universal quantifiers, A note on commutative multivariate rational series, Practical complexities of probabilistic algorithms for solving Boolean polynomial systems, Decision Problems for Finite Automata over Infinite Algebraic Structures, Absoluteness of subword inequality is undecidable, Semi-algebraic sets of $f$-vectors, What is a universal computing machine?, Constructive mathematics and mathematical logic. Part X. Transl. from the Russian, On the theories of free solvable groups, The computational complexity of some problems of linear algebra, Learning via finitely many queries, Sound and complete qualitative simulation is impossible, Compiling dyadic first-order specifications into map algebra