|
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-bFuDs+w6f7qyFYQ//lMQZg@xxxxxxxxxxxxxxxx> 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-+I05ep9qJbk3uPMLIKxrzw@xxxxxxxxxxxxxxxx
http://www.cs.nyu.edu/mailman/listinfo/fom
_______________________________________________
FOM mailing list
FOM-+I05ep9qJbk3uPMLIKxrzw@xxxxxxxxxxxxxxxx
http://www.cs.nyu.edu/mailman/listinfo/fom
|
