Re: ranges of integer polynomials

On Sun, 07 Oct 2007 10:26:11 -0700, adler.math@xxxxxxxxx wrote:

On Oct 6, 4:46 pm, quasi <qu...@xxxxxxxx> wrote:
However here's an argument that should work ...

Let P be an integer polynomial such that it's undecidable whether or
not the diophantine equation P = 0 has integer solutions. Such a
polynomial must exist by the results of Matiyasevich.

Then, letting

f = 1 + P^2

it must be undecidable whether or not 1 is in range(f), hence range(f)
is a subset of N, but not recursive.


The argument misunderstands the meaning of the term "undecidable". I
need to explain what the Matijasevic result says. There is a
polynomial P(x, y_1, \dots, y_n) such that the set of all x for which
there exist y_1, \dots, y_n such that P(x, y_1, \dots, y_n) = 0 is not
recursive. The presence of the parameter x is crucial.

Thus, for the f = 1 + P^2, the set of values of the parameter x such
that 1 is in the range of f is not recursive. However, it is easy to
arrange for the range of f to be recursive for all values of the
parameter x, indeed to consist of all numbers of the form 1 + k^2.

"Undecidable" in this context means that there is no algorithm for
solving a certain infinite class of problems. There is another
meaning of "undecidable," unfortunately. The second meaning of
"undecidable" is "neither provable nor refutable in a certain axiom
system." The two notions of "undecidable" are essentially unrelated.
However, it is easy to confuse them, partly because one path to
showing that there are formally undecidable propositions in, say, a
recursively axiomatized version of arithmetic is to use the
observation that if the theory were complete, then it would be
decidable (in the Turing machine sense).

Thanks for the clarification.

My "proof" did seem too easy. In any case, you showed how the result
can actually be achieved.

quasi

P.S. Thanks for accepting the posting "standards". As I'm sure you've
already noticed, they are only semi-standard, but your current reply
is fine, in my opinion. If you browse the posts of the respected
regulars (as to who they are, you can judge for yourself), you'll see
some variations, but mostly a common style for the structure of posts
and replies.
.

Relevant Pages

  • Re: ranges of integer polynomials
    ... not the diophantine equation P = 0 has integer solutions. ... The argument misunderstands the meaning of the term "undecidable". ... The presence of the parameter x is crucial. ...
    (sci.math)
  • Re: Cascading errors at Buyers "Royal Ark"
    ... you have given up your declared intention of not reading my ... posts and advising others how not to do the same. ... You will see the renunciations/relinquishments by the people concerned. ... there is no need becaue the meaning is the same. ...
    (alt.talk.royalty)
  • Re: those who live by the speed camera ....
    ... - I used the word 'if', meaning I understand it may not be ... I would be interested in 15 posts from you if you did not repeat ... Listen smartass, cautious is often used these days to mean slow. ... sarcastic twit ...
    (uk.rec.driving)
  • Re: More units of measure: acres
    ... I also recall him saying something recently that suggested that any aue ... posts with antedatings. ... themselves if they're in the major databases, ... a new meaning is generally ...
    (alt.usage.english)
  • Re: When is a Quaker a Quaker?
    ... And sometimes take statements made in a forum such as this as meaning ... Thought experiments and hypotheticals exist. ... was unclear) but puonding on the author after dozens of posts ...
    (soc.religion.quaker)
Quantcast