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
|
