A74980, A74981, and recursive enumerability
Jud McCranie
judmccr at bellsouth.net
Thu Oct 10 18:57:42 CEST 2002
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?
+---------------------------------------------------------+
| Jud McCranie |
| |
| Programming Achieved with Structure, Clarity, And Logic |
+---------------------------------------------------------+
More information about the SeqFan
mailing list