The discussion centers on the decidability of finite sets of natural numbers and the termination of algorithms designed to check membership within these sets. It is established that any finite set is effectively decidable, meaning an algorithm can be constructed to determine if a number belongs to the set. The algorithm will terminate after a maximum of 'n' comparisons, where 'n' is the size of the finite set. If the input number is not included in the set, the algorithm will still terminate after checking all elements.
PREREQUISITESStudents and professionals in computer science, particularly those interested in algorithms, computational theory, and mathematical logic.
agapito said:A theorem states: Any finite set of natural numbers is effectively decidable. I understand the construction of the (brute force) algorithm to check every input for inclusion in the set. However, if the input is not included in the set, the algorithm would not terminate, and we require algorithms to terminate. What am I missing here?
I like Serena said:Hi agapito, welcome to MHB, (Wave)
When you say 'a theorem states', can you please clarify which theorem you're referring to?
And when you say 'Any finite set of natural numbers is effectively decidable', can you clarify what you mean by natural numbers being decidable? As I see it, a number does not decide anything.
Country Boy said:What ever number is given, you only need to check it against the "n" numbers in the finite set. If the number is in the set that might be determined in less than n comparisons. If the number is not in the set that will be determined in n comparisons.