• Cows Look Like Maps@sh.itjust.works
      link
      fedilink
      English
      arrow-up
      5
      arrow-down
      1
      ·
      edit-2
      7 months ago

      In fact, there’s infinite problems that cannot be solved by Turing machnes!

      (There are countably many Turing-computable problems and uncountably many non-Turing-computable problems)

      • MBM@lemmings.world
        link
        fedilink
        English
        arrow-up
        1
        arrow-down
        2
        ·
        7 months ago

        Infinite seems like it’s low-balling it, then. 0% of problems can be solved by Turing machines (same way 0% of real numbers are integers)

        • Cows Look Like Maps@sh.itjust.works
          link
          fedilink
          English
          arrow-up
          2
          ·
          7 months ago

          Infinite seems like it’s low-balling it

          Infinite by definition cannot be “low-balling”.

          0% of problems can be solved by Turing machines (same way 0% of real numbers are integers)

          This is incorrect. Any computable problem can be solved by a Turing machine. You can look at the Church-Turing thesis if you want to learn more.

          • MBM@lemmings.world
            link
            fedilink
            English
            arrow-up
            1
            ·
            7 months ago

            Infinite by definition cannot be “low-balling”.

            I was being cheeky! It could’ve been that the set of non-Turing-computible problems had measure zero but still infinite cardinality. However there’s the much stronger result that the set of Turing-computible problems actually has measure zero (for which I used 0% and the integer:reals thing as shorthands because I didn’t want to talk measure theory on Lemmy). This is so weird, I never got downvoted for this stuff on Reddit.

        • DaleGribble88@programming.dev
          link
          fedilink
          English
          arrow-up
          1
          ·
          7 months ago

          The subset of integers in the set of reals is non-zero. Sure, I guess you could represent it as arbitrarily small small as a ratio, but it has zero as an asymptote, not as an equivalent value.

          • MBM@lemmings.world
            link
            fedilink
            English
            arrow-up
            1
            ·
            7 months ago

            The cardinality is obviously non-zero but it has measure zero. Probability is about measures.

    • vzq@lemmy.blahaj.zone
      link
      fedilink
      English
      arrow-up
      5
      arrow-down
      2
      ·
      7 months ago

      Except they have convinced themselves that if it can’t be calculated it’s worthless.