Proof of Impossibility - Does This Diophantine Equation Have An Integer Solution? Hilbert's Tenth Problem

Does This Diophantine Equation Have An Integer Solution? Hilbert's Tenth Problem

For reference until this entry can be better constructed see Franzén pages 70–71.

This problem is related to Fermat's last theorem, only recently proved by Andrew Wiles (1994). Previously in his book (p. 10, 11) Franzén describes what a Diophantine equation is and gives good examples (Fermat's last theorem has to do with a simple type of Diophantine equation recognizable to students as part of the conclusion of the Pythagorean theorem when the exponent is "2").

Question: Does any arbitrary "Diophantine equation" have an integer solution? Answer: undecidable.
Fermat's last theorem: "No equation of the form
xn + yn = zn with n greater than 2 have any solution in positive integers" (Franzén p. 11)

Franzén introduces "Hilbert's 10nth problem" and the MRDP theorem (Matiyasevich-Robinson-Davis-Putnam theorem) which states that no algorithm exists which can decide whether or not a Diophantine equation has any solution at all. Franzén's treatment is a creditable job but relies on the reader's understanding of certain terminology with reference to Turing's theorem that he develops a few pages beforehand: MRDP uses the undecidability proof of Turing: "... the set of solvable Diophantine equations is an example of a computably enumerable but not decidable set, and the set of unsolvable Diophantine equations is not computably enumerable" (p. 71).

Franzén also introduces a really fun unsolved problem, very easy to describe—even an elementary-algebra student in junior high could get the question: the Collatz conjecture (3n + 1 conjecture, Ulam's problem). That something so easy to describe and fun to fiddle with is unsolved is rather shocking! (Franzén, p. 11).

Read more about this topic:  Proof Of Impossibility

Famous quotes containing the words tenth, problem and/or equation:

    The tenth day of Christmas,
    My true love sent to me
    Ten pipers piping,
    —Unknown. The Twelve Days of Christmas (l. 64–66)

    The perfect detective story cannot be written. The type of mind which can evolve the perfect problem is not the type of mind that can produce the artistic job of writing.
    Raymond Chandler (1888–1959)

    Jail sentences have many functions, but one is surely to send a message about what our society abhors and what it values. This week, the equation was twofold: female infidelity twice as bad as male abuse, the life of a woman half as valuable as that of a man. The killing of the woman taken in adultery has a long history and survives today in many cultures. One of those is our own.
    Anna Quindlen (b. 1952)