[FOM] Could it be that a "typical" Diophantine set is computable?
Timothy Y. Chow
tchow at alum.mit.edu
Sun Jul 2 20:36:24 EDT 2017
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?
This question came up indirectly on MathOverflow:
https://mathoverflow.net/questions/115430/what-is-the-geometry-of-an-undecidable-diophantine-equation
One respondent was surprised when I stated my expectation that
undecidability was "generic"; he said that in the context of combinatorial
group theory, there is a condition called "hyperbolicity" that (a) is
"probabilistically generic" and (b) implies the solvability of all the
usual problems (word problem, isomorphism problem, etc.). So perhaps I'm
wrong that "average" Diophantine sets are not computable.
Tim
More information about the FOM
mailing list