Publication:3992465

Publication date: 23 January 1993

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

11U05: Decidability (number-theoretic aspects)

12L05: Decidability and field theory

11-02: Research exposition (monographs, survey articles) pertaining to number theory

03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations

03B25: Decidability of theories and sets of sentences

11D99: Diophantine equations

Related Items

Economic Dynamics and Computation—Resurrecting the Icarus Tradition, REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS, The concept of truth in a finite universe, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases, Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem, The computational status of physics, On pseudo algebraically closed extensions of fields, Learning via finitely many queries, Sound and complete qualitative simulation is impossible, On the solvability of a class of Diophantine equations and applications, Graph compression and the zeros of polynomials, Affine linear sieve, expanders, and sum-product, Mechanically proving termination using polynomial interpretations, Inferring answers to queries, \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, On deciding stability of multiclass queueing networks under buffer priority scheduling policies, Existential arithmetization of Diophantine equations, A note on commutative multivariate rational series, What is a universal computing machine?, On the theories of free solvable groups, The computational complexity of some problems of linear algebra, A direct method for simulating partial recursive functions by Diophantine equations, Diophantine representations of linear recurrences. I, Hypercomputation with quantum adiabatic processes, Hypercomputation by definition, Constructive mathematics and mathematical logic. Part X. Transl. from the Russian, On two-way nondeterministic finite automata with one reversal-bounded counter, Infiniteness sets of primes, admitting diophantine representations in eight variables, A new technique for obtaining diophantine representations via elimination of bounded universal quantifiers, Compiling dyadic first-order specifications into map algebra, Learning power and language expressiveness., On two-way FA with monotonic counters and quadratic Diophantine equations, On the complexity of decision using destinies in \(H\)-bounded structures, Hilbert's problems and their sequels, On an undecidable problem related to difference equations with parameters, Solving word equations modulo partial commutations, Diophantine representations of linear recurrent sequences. II, Uncomputably large integral points on algebraic plane curves?, Transformations of normal and inverted function tables, 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, The case for hypercomputation, Embedding infinitely parallel computation in Newtonian kinematics, Church's thesis meets the \(N\)-body problem, Quantum principles and mathematical computability, ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS, MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM