117b – Undecidability and Incompleteness – Lecture 4

We showed that is Diophantine. This implies that the prime numbers are Diophantine. Therefore, there is a polynomial in several variables with integer coefficients whose range, when intersected with the natural numbers, coincides with the set of primes. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.

We proved the bounded quantifier lemma, the last technical component of the proof of the undecidability of Hilbert’s tenth problem. It implies that the class of relations definable by a formula in the structure coincides with the class of relations (i.e., the Diophantine ones).

To complete the proof of the undecidability of the tenth problem, we will show that any c.e. relation is Diophantine. For this, recall that a set is c.e. iff it is the domain of a Turing machine. We proceeded to code the behavior of Turing machines by means of a Diophantic representation. This involves coding configurations of Turing machines and it remains to show how to code the way a configuration changes into another one.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Thursday, February 1st, 2007 at 2:51 pm and is filed under 117b: Computability theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

4 Responses to 117b – Undecidability and Incompleteness – Lecture 4

I was a bit confused about this in class, but it’s probably just because I was majorly sleep-deprived: “Therefore, there is a polynomial in several variables with integer coefficients whose range on the natural numbers coincides with the prime numbers. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.”

The distinction, then, is that there IS a polynomial whose range is all the primes AND a bunch of negatives, but there is NO polynomial whose range is primes only? Is that correct?

Yes, exactly. I think I may have actually written something incorrect on the board, so I will briefly review it on Tuesday. We have that the primes are Diophantine. From this, we saw how to build a polynomial P such that, if R is its range, then the intersection of R with the naturals is the set of primes. But any such R necessarily takes negative values (and 0?) as well. I rephrased the entry a little to make this clear.

If anyone’s interested, I remembered reading about this polynomial (though I didn’t know the historical context in which it was derived) a while back in the book The Music of the Primes. According to Amazon’s search-inside-this-book function, it’s on page 200, which I have downloaded from Amazon and is now stored on my web page. It’s good to see these things actually written out!

Thanks!
The same polynomial is shown in page 331 of the handout “Hilbert’s tenth problem. Diophantine equations: positive aspects of a negative solutions”, it is due to J. P. Jones. The polynomial we obtain if we simply apply the definitions shown in lecture is different than this one.
It is curious that this polynomial is written as the product of two polynomials, and yet its (positive) values are precisely the prime numbers.

(1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038). Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternat […]

Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Un […]

I am looking for references discussing two inequalities that come up in the study of the dynamics of Newton's method on real-valued polynomials (in one variable). The inequalities are fairly different, but it seems to make sense to ask about both of them in the same post. Most of the details below are fairly elementary, they are mostly included for comp […]

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

First of all, $f(z)+e^z\ne 0$ by the first inequality. It follows that $e^z/(f(z)+e^z)$ is entire, and bounded above. You should be able to conclude from that.

Yes. The standard way of defining these sequences goes by assigning in an explicit fashion to each limit ordinal $\alpha$, for as long as possible, an increasing sequence $\alpha_n$ that converges to $\alpha$. Once this is done, we can define $f_\alpha$ by diagonalizing, so $f_\alpha(n)=f_{\alpha_n}(n)$ for all $n$. Of course there are many possible choices […]

I disagree with the advice of sending a paper to a journal before searching the relevant literature. It is almost guaranteed that a paper on the fundamental theorem of algebra (a very classical and well-studied topic) will be rejected if you do not include mention on previous proofs, and comparisons, explaining how your proof differs from them, etc. It is no […]

No, the rank of a set $x$ is the least $\alpha$ such that $x\in V_{\alpha+1}$. Note that if $\alpha$ is limit, any $x\in V_\alpha$ belongs to some $V_\beta$ with $\beta

I was a bit confused about this in class, but it’s probably just because I was majorly sleep-deprived: “Therefore, there is a polynomial in several variables with integer coefficients whose range on the natural numbers coincides with the prime numbers. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.”

The distinction, then, is that there IS a polynomial whose range is all the primes AND a bunch of negatives, but there is NO polynomial whose range is primes only? Is that correct?

Yes, exactly. I think I may have actually written something incorrect on the board, so I will briefly review it on Tuesday. We have that the primes are Diophantine. From this, we saw how to build a polynomial P such that, if R is its range, then the intersection of R with the naturals is the set of primes. But any such R necessarily takes negative values (and 0?) as well. I rephrased the entry a little to make this clear.

If anyone’s interested, I remembered reading about this polynomial (though I didn’t know the historical context in which it was derived) a while back in the book The Music of the Primes. According to Amazon’s search-inside-this-book function, it’s on page 200, which I have downloaded from Amazon and is now stored on my web page. It’s good to see these things actually written out!

Thanks!

The same polynomial is shown in page 331 of the handout “Hilbert’s tenth problem. Diophantine equations: positive aspects of a negative solutions”, it is due to J. P. Jones. The polynomial we obtain if we simply apply the definitions shown in lecture is different than this one.

It is curious that this polynomial is written as the product of two polynomials, and yet its (positive) values are precisely the prime numbers.