Reduction of an arbitrary diophantine equation to one in 13 unknowns

DOI10.4064/aa-27-1-521-553zbMath0279.10019OpenAlexW1522991784MaRDI QIDQ4404975

Julia Robinson, Yu. V. Matiyasevich

Publication date: 1975

Published in: Acta Arithmetica (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/205362

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Higher degree equations; Fermat's equation (11D41) Applications of computability and recursion theory (03D80)

Related Items (27)

A direct method for simulating partial recursive functions by Diophantine equations ⋮ Further results on Hilbert's tenth problem ⋮ Diophantine questions in the class of finitely generated nilpotent groups ⋮ Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets ⋮ Index sets and presentations of complexity classes ⋮ Prime representing polynomial ⋮ Diophantine representations of linear recurrences. I ⋮ The quest for Diophantine finite-fold-ness ⋮ Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two ⋮ Undecidability of the submonoid membership problem for free nilpotent group of class $l\geqslant 2$ of sufficiently large rank ⋮ Primes are nonnegative values of a polynomial in 10 variables ⋮ A new proof of the theorem on exponential diophantine representation of enumerable sets ⋮ On a theorem of Matiyasevich ⋮ Diophantine representation of perfect numbers ⋮ Skolem functions of arithmetical sentences. ⋮ On the zero-inequivalence problem for loop programs ⋮ ON GENERIC COMPLEXITY OF DECIDABILITY PROBLEM FOR DIOPHANTINE SYSTEMS IN THE SKOLEM’S FORM ⋮ Computational complexity of winning strategies in two-person polynomial games ⋮ My collaboration with Julia Robinson ⋮ Unnamed Item ⋮ Diophantine complexity ⋮ NP-complete decision problems for binary quadratics ⋮ Undecidable diophantine equations ⋮ Infiniteness sets of primes, admitting diophantine representations in eight variables ⋮ Definability, decidability, complexity ⋮ Unnamed Item ⋮ Julia Robinson, in memoriam

This page was built for publication: Reduction of an arbitrary diophantine equation to one in 13 unknowns