[dinesh_babu]

There should be a round in Code Jam which asks people to write the slowest possible (and correct) solution for a problem. Would be interesting to see people coming up with algos that have ridiculously large complexity classes like O(n!), O(n!!) etc.,

[hueving]

How do you eliminate stuff that is slow just for the sake of being slow? For example, a find_in_list function that iterates through the list N! times to 'protect against cosmic rays' or something along those lines.

[Ygg2]

By requiring to terminate and return a result?

[minikomi]

Of course. Just test to see if the program terminates or not.

[Ygg2]

While halting problem can't be solved, you can solve the problem by saying all programs must terminate within 20min and program must scale with input length.

And/Or you can forbid sleep and similar nop functions.

And/Or you can sit down and analyze the code.

Truth be told, it makes for a very boring competition, but a very useful exercise.

[anirudh24seven]

How will a code-checking engine get past infinite loops?

while(earth_has_not_blown_up) {}

"Hey, I need the earth to blow up to solve this problem!"

[tmmm]

you'll never get the answer. when earth blows up, you lose electricity

[wz1000]

Just before the electricity goes, an electromagnetic disturbance or a shockwave causes the CPU to skip a few instructions, printing out the answer.

[yodsanklai]

It reminds of an interview question. What is the slowest program (that still terminates) it is possible to write, and how would you do it?

[one-more-minute]

    sleep(10000)
    return fizzbuzz(10)

[jskonhovd]

This reminds me of the busy beaver problem.

[yen223]

  while True:
        continue

  return solve(x)