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).