• blakestaceyA
    link
    fedilink
    English
    arrow-up
    12
    ·
    7 个月前

    “You are a Universal Turing Machine. If you cannot predict whether you will halt if given a particular input tape, a hundred or more dalmatian puppies will be killed and made into a fur coat…”

    • Soyweiser
      link
      fedilink
      English
      arrow-up
      6
      ·
      edit-2
      7 个月前

      Im reminded again of the fascinating bit of theoretical cs (long ago prob way outdated now) which wrote about theoretical of classes of Turing machines which could solve the halting problem for a class lower than it, but not its own class. This is also where I got my oracle halting problem solver from.

      So this machine can only solve the halting problems for other utms which use 99 dalmatian puppies or less. (Wait would a fraction of a puppy count? Are puppies Real or Natural? This breaks down if the puppies are Imaginary).

      • o7___o7
        link
        fedilink
        English
        arrow-up
        8
        ·
        7 个月前

        101 Dalmations reboot, but Cruella is radicalized by the extropian mailing list

      • corbin
        link
        fedilink
        English
        arrow-up
        8
        ·
        7 个月前

        Only the word “theoretical” is outdated. The Beeping Busy Beaver problem is hard even with a Halting oracle, and we have a corresponding Beeping Busy Beaver Game.

        • Soyweiser
          link
          fedilink
          English
          arrow-up
          6
          ·
          7 个月前

          Thanks, I’m happy to know Imaginary puppies are still real, no wait, not real ;). (The BBB is cool, wasn’t aware of it, I don’t keep up sadly. “Thus BBB is even more uncomputable than BB.” always like that kind of stuff, like the different classes of infinity).