3 ms·

It’s fun to think about. What about the Collatz conjecture? If we run it for arbitrary n, on a computer that represents numbers up to n_max, we could know if it

It’s fun to think about. What about the Collatz conjecture? If we run it for arbitrary n, on a computer that represents numbers up to n_max, we could know if it will halt within n_max steps. Since only n_max numbers are representable, we could track all visited numbers to detect any cycle that might occur. If on the other hand any iteration would exceed n_max, then the program would halt by crashing. hailstone :: Integer -> Integer hailstone n | n `mod` 2 == 0 = n `div` 2 | otherwise = 3 * n + 1 collatz :: Integer -> Bool collatz n | hailstone n == 1 = True | otherwise = collatz (hailstone n) Edit: however, you would need enough disk space to store the cycle-detection index.

kaba0 3y ago
We have actually done something like that up to the 32bit n_max for sure (but maybe even 64bit?), without any number that would contradict the conjecture. But yeah, it is not even trivial to say whether it has a bounded max memory, so in case of an arbitrary precision int type, it may not be LBA, but Turing?
- odyssey7 3y ago
  I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one. We can actually do it in O(1) space complexity in exchange for higher time complexity. For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_max to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n * n_max), or constant complexity depending on how you look at it, but it only requires storing a single n_i at a time for cycle detection. But then again, if you actually loop for n_max iterations without halting by reaching 1 or crashing, then you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.

kaba0 3y ago

We have actually done something like that up to the 32bit n_max for sure (but maybe even 64bit?), without any number that would contradict the conjecture. But yeah, it is not even trivial to say whether it has a bounded max memory, so in case of an arbitrary precision int type, it may not be LBA, but Turing?

odyssey7 3y ago
I guess I was thinking about indexing the visited numbers from a graph-traversal-algorithm-interview perspective instead of a CS theory one. We can actually do it in O(1) space complexity in exchange for higher time complexity. For i in range 1..n, compute n_i, the ith number in the hailstone iteration, and then continue the hailstone iteration n_(i+1)..n_max to see if n_i is equal to any of them. This takes us to quadratic time complexity, O(n * n_max), or constant complexity depending on how you look at it, but it only requires storing a single n_i at a time for cycle detection. But then again, if you actually loop for n_max iterations without halting by reaching 1 or crashing, then you had to reuse a number somewhere, so the explicit cycle detection isn’t really important.