Earlier quoted context omitted.
Why would that be bounded far below modern memory limits? Why would that be bounded at all ? Secondly, you're making the logic error A => B implies not A => not B. If state spaces as large as modern memory limits allow are too large, that doesn't imply that state spaces far below modern memory limits are small enough to handle. Thirdly, your program trivially terminates doing nothing.
Troll-feeding time! Pretend that an OOM condition is the same as a False answer. :3 Here's a program, building on the previous one, which either terminates or doesn't. from itertools import count for i in count(1): if not is_collatz(i): break
I can tell you now that your code terminates. The set s is strictly increasing in size, inevitably going towards an OOM condition if the loop doesn't terminate by other means. Note that we are talking about determining halting or not halting, not with which value the program halts.
This is not a troll. You tried to respond with something witty. I just pointed out that in this case things like the collatz conjecture don't apply, because it is a conjecture over all natural numbers. When you are working with finite memory, there is no way to encode this conjecture into a program (e.g. by making it halt if the conjecture is true and making it loop when the conjecture is false).