To get a sense of how far one could push these fruit problems, see Matiyasevich’s Theorem (<a href="http://www.scholarpedia.org/article/Matiyasevich_theorem" rel="nofollow">http://www.scholarpedia.org/article/Matiyasevich_theorem</a>).<p>My understanding is a bit fuzzy, but it basically says you can encode any recursively enumerable set in terms of solutions to Diophantine equations (i.e. integer polynomials).<p>In particular you can encode, say, the set of all Turing Machines which halt in terms of the solutions to some integer polynomial.