A74980, A74981, and recursive enumerability

[Antti Karttunen]

Jud McCranie wrote:
> 
> One characterization of sets that are recursively enumerable (r.e.) but not
> recursive is that their members can be generated, but not in order (whereas
> recursive sets can be listed in order).  Sequences such as A74980 (numbers
> not the difference of squares and/or cubes) and A74981 (numbers not the
> difference of perfect powers) certainly _seem_ to be r.e. but not
> recursive.  Is it possible to prove that sets like these are r.e. but not
> recursive, or would some deeper understanding prove them to be recursive?

I guess the following is related, from:
http://www.cs.bu.edu/fac/lnd/toc/z/node9.html

  "One can show a set r.e.-complete (and, thus, undecidable) by reducing the Halting
Problem to it. So Ju.Matijasevich proved r.e.-completeness of Diophantine Equations
Problem: given a multivariate polynomial of degree 4 with integer coefficients,
find if it has integer roots. The above (and related) concepts and facts are broadly
used in Theory of Algorithms and should be learned from any standard text, e.g., [Rogers 67]. "

Yuri Matiyasevich's paper with its consequences is also mentioned in:

http://mathworld.wolfram.com/DiophantineEquation.html

See that.


Terveisin,

Antti