• xigoi@lemmy.sdf.org
    link
    fedilink
    arrow-up
    95
    ·
    1 year ago

    “The other programmers keep accidentally writing code that ends up in an infinite loop. I'd like you to make a program that can reliably detect that.”

    • elvith@feddit.de
      link
      fedilink
      arrow-up
      32
      ·
      1 year ago

      You may joke, but if I had a penny for every time someone asked me to solve a problem, that basically boils down to the halting problem, I'd be rich.

    • jeff 👨‍💻@programming.dev
      link
      fedilink
      English
      arrow-up
      10
      arrow-down
      3
      ·
      1 year ago

      A full solution to the halting problem can't exist. But you can definitely write a program that will "reliably" detect them to a certain percentage.

      And many applications do exactly that. Firefox asked me today if I wanted to stop a tab because it was processing for too long.

      • bleistift2@feddit.de
        link
        fedilink
        English
        arrow-up
        22
        arrow-down
        1
        ·
        1 year ago

        That’s not even close to solving the halting problem. FF doesn’t check if the program has been in its current state before. It literally just checks if 10 seconds have passed without JS emptying its event loop.

        • jeff 👨‍💻@programming.dev
          link
          fedilink
          English
          arrow-up
          10
          arrow-down
          1
          ·
          1 year ago

          Right. There is no solution to the halting problem, that's been proven. But you just showed you can very easily create a way of practically solving it. Just waiting for 10 seconds does it. That will catch every infinite loop while also having some false positives. And that will be fine in most applications.

          My point is that even if a solution to the halting problem is impossible, there is often a very possible solution that will get you close enough for a real world scenario. And there are definitely more sophisticated methods of catching non-halting programs with fewer false positives.

          • xigoi@lemmy.sdf.org
            link
            fedilink
            arrow-up
            4
            arrow-down
            2
            ·
            1 year ago

            And that will be fine in most applications.

            Have you never written a useful program that took more than 10 seconds to complete?

            • bleistift2@feddit.de
              link
              fedilink
              English
              arrow-up
              5
              ·
              1 year ago

              I fully agree with your sentiment. But just in case: If you’re blocking the main thread of a browser for seconds at a time, you should look into that.

      • xigoi@lemmy.sdf.org
        link
        fedilink
        arrow-up
        8
        ·
        1 year ago

        For JavaScript apps, stopping them when they consume too much resources is definitely a good idea. But if you work on some project where it's common to run computionally intensive tasks, it can be harder to detect non-halting.

    • float@feddit.de
      link
      fedilink
      arrow-up
      5
      ·
      edit-2
      1 year ago

      Just because it's not possible on a Turing Machine doesn't mean it's impossible on a PC with finite memory. You just have to track all the memory that is available to the algorithm and once you detect a state you've seen already, you know it's not halting ever. The detection algorithm will need an insane amount of memory though.

      Edit: think about the amount of memory that would need. It's crazy but theoretically possible. In real world use cases only if the algorithm you're watching has access to a tiny amount of memory.

    • mindbleach@sh.itjust.works
      link
      fedilink
      arrow-up
      1
      ·
      1 year ago

      There have been genuine efforts to do that. Obviously (well, for a very niche use of "obviously") it's not always possible, but detecting infinite loops isn't like the uncertainty principle.

      It's called The Terminator.