Decidability of "Is n divisible with 23?"

I have the following problem:

Let n be a natural number, n > 10^100. Is n divisible with 23?

Is this problem semi-decidable or decidable?

It is possible to create an algorithm to find the answer such that it would always halt. I am pretty confused regarding the difference between semi-decidable and decidable. As far as I understand, a problem is decidable if I can build a Turing machine (algorithm) that would accept the solutions of the problem and otherwise reject. However, if the machine would never halt in the case of inputs that are not solutions, it means that the problem is semi-decidable.

So, I would say that the problem above is decidable but I have no idea if what I said is correct. Can you please help me find out the answer and why? Thank you.

You are correct. A problem is decidable if you can write an algorithm that, for any input, will always make a decision eventually. For the problem of "is n divisible by 23?", consider the following (bad) algorithm: start with i = 1, and check if 23 * i is less than, greater than, or equal to n.

• If it's less than n, increment i.
• If it's equal to n, return true.
• If it's greater than n, return false.

No matter how large n is, this algorithm will always spit out an answer eventually, because you can only increment i a finite number of times before 23 * i is greater than n. It may take a huge amount of time, but for the purposes of decidability we don't care. So this algorithm always makes a decision; thus, the problem is decidable.

Contrast this with semi-decidable problems. These are problems where there exists an algorithm that will always answer true if that's the correct answer, but might run forever if the correct answer is false.

The most famous semi-decidable problem is the Halting Problem: given a program, determine if that program ever stops running. Suppose you try to solve this problem by writing a program that executes its input. If that execution terminates, then you can return true: you know the program terminates because you just watched it do so. But if you've waited around for a while and it hasn't terminated, you can never be sure if it won't terminate if you just let it run a little longer, so you just have to wait. Therefore, if the input program doesn't terminate, your program won't either.

Thus, there's an algorithm for the Halting Problem that always returns true if the actual answer is true, but runs forever if the actual answer is false. Therefore, the Halting Problem is semi-decidable.