The never-ending finite loop | Hacker News Reader

The never-ending finite loop

daemonology.net

57 pointscperciva22 comments

I was kind of disappointed in this article. He starts off with "It's easy to write a loop which looks infinite but in fact completes quite quickly..." which makes it sound like he's going to write a loop that looks finite but in fact spins forever (maybe because of some trick like the integer overflow he uses at the beginning). That would have been interesting.

This is just trying to write a short program that'll run for a long time. Meh.

Here's a 43-character solution.

    for(int x[99]={1};!x[98];++*x)*x*=!++x[*x];

Aha! 42 characters!

    for(int x[99]={1};++x[++*x]?*x=1:!x[98];);

Aah! 40 characters!

    for(int x[99]={98};++x[*x]?*x=98:--*x;);

Sigh. 39 characters!

    for(int x[99]={1};++x[*x]?*x=98:--*x;);

As someone points out in the comments, isn't this true of any NP-complete problem with large enough inputs? This isn't all that surprising then.

You can write a finite-but-longer-than-the-universe loop using any non-constant problem with large enough inputs. There are classes harder than NP, so NP-completeness is not particularly relevant.

As a side note, you're partly assuming in that statement that P != NP, which is yet to be determined in either direction.

He's not. Any program code written today that solves an NP-hard problem without exploiting special properties of the input data will take exponential time. If we discover a smart way to do NP-hard problems in polynomial time, we'll have a better solution for the problem, but the old program code will stay the same.

If you want an analogy: sorting an array is clearly a task that can be solved in O(n log n) time, but if you write a bubble sort implementation (or any other O(n^2) algorithm), the program will still take O(n^2) time.

Right conclusion, not the most direct argument. NP is a proper subset of EXPTIME; there are problems that must take exponential time to complete. Wikipedia says that asking whether a Turing-machine halts in k steps is EXPTIME-complete (you have to execute k steps and the input is of size log k), but if you're willing to fudge a bit and consider function problems, listing all paths in a graph (or something even simpler, like "list all n-bit binary numbers")is going to take exponential time in the worst case.

Any program code written today that solves an NP-hard problem without exploiting special properties of the input data will take exponential time. If we discover a smart way to do NP-hard problems in polynomial time, we'll have a better solution for the problem, but the old program code will stay the same.

You could write a program that runs in polynomial time, but be unable to prove that it does. Then, later, you could find a proof that the program runs in polynomial time. In fact, if P=NP, you can write such a program right now:

    for each string s in the enumeration of all strings {
      if (s = p + q where
          (p is a program and
           q is a proof that p solves 3SAT in polynomial time)) {
        run p on the input;
        return;
      }
    }

Also, you could interleave the execution of this program with one that solves 3SAT in exponential time. Then you'll have a program that works in any case, and that solves 3SAT in polynomial time if P = NP.

I think you can save 2 characters. Here is the original

  char i,x[99];for(x[98]=i=1;x[98];i++)i*=!++x[i];

Here is my improved version

  int i,x[99];for(x[98]=i=1;x[98];)i*=!++x[i++];

your "improved" version illegally modifies 'i' twice in the same statement; its results are undefined.

You are right. But there are two outcomes I think are likely. The ++ could happen either before or after the * . Under either outcome the loop is finite in theory but not practice.

The possibility that I consider unlikely, of course, is that I've broken some assumption that causes the compiler to optimize cause an entirely undefined third behavior (such as crashing). Then the outcome is undefined. That is the kind of implementation detail that code golf often brushes against. I'm not sure whether a solution that includes that possibility but which happens to work on, say, gcc is considered legal.

But that suggests the following unambiguous form:

    int i,x[99];for(x[98]=i=1;x[98];)i*=!++x[++i];

That's still not unambiguous. Turn -Wall on and you'll be told the operation on 'i' may be undefined.

> But there are two outcomes I think are likely.

It's undefined behavior. Any outcome is likely. The compiler could halt your program immediately if it wanted to, and that's just as likely as either of the cases you offer.

And you could save an additional character by changing the loop test to a+b form, i.e.:

int i,x[99];for(x[98]=i=1;x+98;)i*=!++x[i++];

The other array references are l-values.

That would need to be *(x+98), which is longer than x[98].

Ahh.. you're right, of course. What I wrote has an undefined termination condition, besides not being consistent with the original algo. Thanks.

Not very interesting post. I could think of teens of problems out of the top of my head that are theoretically finite but there's no enough mass/energy in the universe for them to complete (like generating a program that solves chess).

His first example of "for (int i = 1; i > 0; i++);" Would be matched by some ugly trick like:

int i = 0; while (!i);

That's warranted to halt as the chances for a bit in i to be flipped by cosmic rays tends to be 1 over time.

The "first example" is merely a preliminary; it isn't an example of what he's actually trying to do. He's trying to write a very short program that (1) is valid C, (2) would terminate eventually on a system that perfectly implements C semantics and can run as long as it wants, but (3) would take so long to do so that no physically realisable system within the observable universe could enable it to run to completion.

You are of course welcome to find this uninteresting, but "I can think of lots of big complicated programs that would terminate but not do so for a very long time" and "In the real world, an infinite loop may terminate because of a hardware malfunction" don't seem to me like good reasons for finding it uninteresting.

How long would it take, exactly, to increment a uint128 until it overflows?

Reply on news.ycombinator.com