Hilbert's tenth problem
Statement
Fix an effective encoding of polynomials with integer coefficients in finitely many unknowns by finite strings over a finite alphabet (so that, for each , every has a code, and the coefficients and the number of unknowns can be read off from the code). Let
the set of polynomial Diophantine equations that are solvable in rational integers.
Call a set of codes decidable if there is a Turing machine that halts on every input string and outputs on inputs in and on inputs not in .
Then the set of codes of members of is not decidable: there exists no algorithm which, given as input an arbitrary Diophantine equation with any number of unknowns and with rational integral coefficients, determines in a finite number of operations whether the equation is solvable in rational integers.
The same holds with replaced by , i.e. for solvability in non-negative integers. Moreover, undecidability persists in a fixed one-parameter family: there is a polynomial with integer coefficients such that the set
is not computable.
Equivalently, in terms of Diophantine sets: a set is called Diophantine if there are and a polynomial with integer coefficients such that
every recursively enumerable subset of is Diophantine.
Record
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.