The discussion revolves around the termination of an algorithm designed to check membership in a finite set of natural numbers, particularly when the input number is not included in that set. The scope includes theoretical aspects of decidability and algorithmic behavior.
Participants express differing views on the termination of the algorithm, with some asserting that it will terminate after a finite number of checks, while others remain uncertain about the implications of the algorithm's behavior when the input is not in the set.
The discussion includes assumptions about the nature of decidability and the behavior of algorithms, which may not be fully articulated or agreed upon by all participants.
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.