[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 

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


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:


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.


More information about the FOM mailing list