2

A pair of twin primes is defined as (p, p+2) where both p and p + 2 are prime.
Given $S = \{i\in Z^+ | i\, is\, one\, of\, a\, pair\, of\, twin\, primes\}$
Is S decidable?

My understanding is that S(language) is decidable if there exists some method to determine whether a given i(word) is in S. To prove that S is decidable, would it suffice for us to prove that there is a method(algorithm) to prove whether or not (i, i+2) or (i-2, i) are a pair of twin primes?

Carl Mummert
  • 81,604
EggHead
  • 667

1 Answers1

2

It is decidable. To check whether $n$ is prime, it is enough to check, for every integer $k$ such that $1\lt k\lt n$, whether $k$ divides $n$. (There are far more efficient algorithms. But all we need to do is to show that there is an algorithm.)

André Nicolas
  • 507,029