[FOM] Decidability of Diophantine equations
franklin.vp at gmail.com
Thu Dec 14 16:21:39 EST 2006
Well, single quadratic Diophantine equations are decidable.
I think Gauss discussed this case. I read that there is a number n such that
a equation in n variables
is not decidable. If I remember well n=9 or so.
Franklin Vera Pacheco
(Frank cheValier on a Pc)
address:45 #10029 e/100 y104 Marianao, C Habana, Cuba
phone: 260 6043
summa cum laude in mathematics; highest honors in mathematics
University of Havana
On 12/14/06, Andrej Bauer <Andrej.Bauer at fmf.uni-lj.si> wrote:
> 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
> FOM mailing list
> FOM at cs.nyu.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM