Is this imply that this problem of twin primes is Partially Decidable

143 Views Asked by At

I find this equivalence:

Partially Decidable Problem $⇔$ Recursively Enumerable Set

I know that the set of twin primes is a recursively enumerable set. Is this imply that the problem of the existence of infinitely many twin primes is Partially Decidable.

1

There are 1 best solutions below

4
On BEST ANSWER

No. The reason for this is because there is no known way to detect if there are infinitely many twin primes even though we can find twin primes in a recursively enumerable way. So the problem of enumerating the twin primes is recursively enumerable but the problem of deciding if there are finitely many or infinitely many isn't by any known algorithm.