Can we decide if a number n belongs to a countable set S?

78 Views Asked by At

The question at hand is the following:

Let S be a subset of N (natural numbers), so it is infinite and countable. Let Ls={a^n | n belongs to S} a language. Is Ls recursive? Is Ls recursively enumerable? Justify your answers.

I'm pretty sure that Ls is recursive for any S, because we can write a program that decides Ls (or a Turing Machine for that matter). But how do I justify it?

1

There are 1 best solutions below

0
On

No, you cannot. There are simple, absolutely computable isomorphisms between strings and numbers (e.g. for alphabet of size n, take the strings as numbers in base n plus some cosmetics for leading zeroes). So if all sets of numbers were decidable or enumerable, all sets of strings would be so, too.