[FOM] Decidability of Diophantine equations

Andrej Bauer Andrej.Bauer at fmf.uni-lj.si
Thu Dec 14 06:12:16 EST 2006

Dear FOMers,

as is well-known, solvability of general Diophantine systems is 
undecidable. But what is known about particular kinds of systems, or 
even single equations? For example:

1) Is it decidable whether a single quadratic Diophantine equation has a 
solution? Has a solution in non-negative integers?

2) If a system has a small number of variables, say two or three, is its 
solvability decidable?

3) What if we combine 1) and 2)?

I am intersted in solutions in natural numbers (not integers), but would 
be interested in knowing anything "positive" that is worth knowing other 
than "Hilbert 10th is undecidable". So far I am aware of the fact that 
systems with a single variable are easy, and that Presburger arithmetic 
is decidable.

I need this for the survey of all small sentences of PA.

Andrej Bauer

More information about the FOM mailing list