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