Decision problem: Existence of a perfect number m larger than a natural number n

81 Views Asked by At

I am currently having a look at the slides from my theoretical computer science lecture and I am having trouble to understand a claim made. According to the slides the language

$L = \{ n \in \mathbb{N} ~|~ \exists~ m: m > n \wedge \text{m is a perfect number} \}$

is decidable even though the total number of perfect numbers is unknown.

Obviously L is semi-decidable as one can start searching for a perfect number $> n$. If there is no such number the algorithmn will never terminate, resulting in the semi-decidability of $L$.

My question would be if there is a different approach allowing to decide $L$, i. e. the algorithmn also terminates when $n \not\in L$ or if the claim made is incorrect.

Edit: Solution (thanks to ToniK and Peter)

$L$ is either finite (if there is a largest perfect number) or equal to $\mathbb{N}$ (if the set of perfect numbers is infinite). By sticking to the definition of decidability one only needs to proof that there is an algorithm deciding whether a concrete $n \in L$ or not. We do not need to provide an algorithm for that - this is just an existential proof. In either case one can decide $L$ (as $L$ is finite or $\mathbb{N}$).

1

There are 1 best solutions below

8
On BEST ANSWER

$L$ is decidable because it is either finite, or the whole of $\Bbb N$. We just don't know which.