On 10/24/18 9:27 PM, Bill Page wrote:
> On Wed, Oct 24, 2018 at 5:05 PM Waldek Hebisch <[email protected]>
> wrote:
>>
>> If you could find solution _in the fraction field_ then
>> the method would be fine. However, in general finding
>> rational solutions to polynomial system of equations is
>> uncomputable.
>
> Can you suggest a reference? I could not find this result (well
> known?) after a quick search.
>
I believe that the Godel problem as implemented by Chaitine actually
constructed a Diophantine equation (and program) that provably couldn't
be proven to have a finite or infinite number of integer solutions.
Since any "solution" could be considered a "factor" then this would
present a problem to a factoring program.
Along the same lines:
From:
https://en.wikipedia.org/wiki/Undecidable_problem#Examples_of_undecidable_problems
"
A Diophantine equation is a more general case of Fermat's Last Theorem;
we seek the integer roots of a polynomial in any number of variables
with integer coefficients. Since we have only one equation but n
variables, infinitely many solutions exist (and are easy to find) in the
complex plane; however, the problem becomes impossible if solutions are
constrained to integer values only. Matiyasevich showed this problem to
be unsolvable by mapping a Diophantine equation to a recursively
enumerable set and invoking Gödel's Incompleteness Theorem.
"
And this is over a fully commutative ring; integers!
RayR
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
