Suppose we fix an alphabet A. If S is a language over alphabet A, the complement S of S is the set A* − S. That is, S is the set of all strings not in S.
When you think of a language as a computational problem, taking the complement just switches the yes and no answers.
For values x ∈ S, you answer yes for problem S, but you answer no for problem S. For values x ∉ S, you answer no for problem S and yes for problem S
It should be clear that, given a program that solves S, you can create a program that solves S. Just go through and change the yes answers to no answers and the no answers to yes answers. So the following are true.
Theorem. If S is computable then S is also computable.
Corollary. If S is uncomputable then S is also uncomputable.
An integer n is prime if n > 1 and the only factors of n are 1 and n. An integer n is composite if n > 1 and n is not prime.
Define
PRIME = {n | n is a prime integer}
NOTPRIME = {n | n is not a prime integer}
COMPOSITE = {n | n is composite}
We have seen that PRIME is computable, and the following program does the job.
isprime(n)
if n < 2 then
return false
else
for k = 2,...,n-1 do
if n mod k = 0 then
return false
end if
end for
return true
end if
So NOTPRIME must also be computable, and it is solved
by the following program.
isnotprime(n)
if n < 2 then
return true
else
for k = 2,...,n-1 do
if n mod k = 0 then
return true
end if
end for
return false
end if
COMPOSITE is not exactly the complement of PRIME, but it is close enough to call it a near-complement. If you are asking whether an integer is prime or composite, the only interesting integers are those that are greater than 1. When restricted to those values, COMPOSITE is PRIME. All we need is a little bit of code to handle the uninteresting numbers.
iscomposite(n)
if n < 2 then
return false
else
for k = 2,...,n-1 do
if n mod k = 0 then
return true
end if
end for
return false
end if