[FOM] Could it be that a "typical" Diophantine set is computable?

[Kreinovich, Vladik]

Here is a possible formal meaning of your statement. Let us effectively enumerate all Diophantine sets, and for some n, let us consider sets S_1, …, S_n in this enumeration.

Cartesian products of Diophantine sets are also Diophantine sets, with a simple pairing function transformation into sets of integers.

For any d, if we consider products S_{i_1} X … X S_{i_d} of d sets S_{i_k}, I _k <= n, then we get n^d possible product sets.

The whole class of Diophantine sets can be obtained if we tend both n and d to infinity.

A Cartesian product A X … X B is decidable if and only if all the sets A, …, B are decidable. Let m(n) denote the number of decidable sets among the first n Diophantine sets S_1, …, S_n. Then out of n^d possible Cartesian products, (m(n))^d are decidable, so the proportion of decidable products is (m(n) / n)^d.

Since some Diophantine sets are undecidable, for large n, we get m(n)  < n and m(n) / d  < 1. Thus, for all sufficiently large n, when d tends to infinity we have (m(n) / n)^d tends to 0, so this proportion tends to 0.  This is true for every n, so the limit of this limit when n --> infinity is also 0.

In this sense, the proportion of decidable sets is 0, and thus, almost all Diophantine sets are undecidable.


> On Jul 2, 2017, at 8:36 PM, Timothy Y. Chow <tchow at alum.mit.edu<mailto:tchow at alum.mit.edu>> wrote:
>
> By the MRDP theorem, a set is Diophantine if and only if it is computably enumerable.
>
> The impression I've gotten---although I don't think I've seen it explicitly asserted anywhere---is that in some sense "most" Diophantine sets are *not* computable.  Are there any results, or even heuristic arguments, in this direction?
>
> Of course it is not clear what I mean by "most Diophantine sets."  One way to make this a little more precise is to imagine that we pick a polynomial
>
>  P(x1,x2,...,xj,y1,y2,...,yk)
>
> with integer coefficients according to some probability distribution and then consider the set of assignments to (x1,x2,...,xj) such that the resulting polynomial in (y1,y2,...,yk) has a zero.  This is still not quite precise because I haven't specified the probability distribution, but you get the idea: Is there some sense in which a "random" or "arbitrary" choice of P will "usually" result in an undecidable problem?
>
> Tim

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170705/4792b4f6/attachment.html>