MIT develops new tool that can interrupt infinite loops

Re:MIT develops new tool that can interrupt infinite loops by MostAwesomeDude on Tuesday August 02, 2011 @06:18PM (#2838937)

  def is_collatz(n):
   s = set()
   while n not in (1, 2, 4):
    if n % 2:
     n = 3 * n + 1
    else:
     n /= 2
    if n in s: # Non-Collatz loop
     return False
    s.add(n)
   return True

This is theoretically bounded far below modern memory limits. Feel free to tell me the first natural number for which it returns False. :3

[ Parent | on HN ]

Re:MIT develops new tool that can interrupt infinite loops by jules on Tuesday August 02, 2011 @08:18PM (#2839250)

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.

[ Parent | on HN ]

Re:MIT develops new tool that can interrupt infinite loops by MostAwesomeDude on Tuesday August 02, 2011 @09:44PM (#2839485)

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

[ Parent | on HN ]

Re:MIT develops new tool that can interrupt infinite loops by jules on Wednesday August 03, 2011 @06:11AM (#2840496)

So how is the state space then much smaller than modern memory limits? That still ignores my second point, namely that the logical reasoning that the xyzzyz somehow implied that programs that have state spaces smaller than modern memory limits are in practice analyzeable for halting/not halting, is not sound.

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).

[ Parent | on HN ]

Re:MIT develops new tool that can interrupt infinite loops by xyzzyz on Wednesday August 03, 2011 @02:23AM (#2840045)

I don't understand your point. I could run it with memory constrained to, say, 100 KB, and it will quickly produce an OOM condition. I clearly said that the approach I sketched in my first comment is not practically applicable.

Real-life computers have bounded memory, so they don't have any more computational power than, say, regular expressions matchers -- every computational task performed by real computer can be represented by appropriately complicated regular expression. That's why one needs to be especially careful when arguing from computability when talking about real-life problems.

The more serious issue is a treatment of I/O.

[ Parent | on HN ]