[FOM] Decidability of Diophantine equations

[Franklin Vera]

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.
Best regards

-- 
Franklin Vera Pacheco
(Frank cheValier on a Pc)
home-page: http://franklin.vp.googlepages.com
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
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20061214/06d920cd/attachment.html