• garyyo@lemmy.world
      link
      fedilink
      arrow-up
      16
      ·
      1 year ago

      Wait till you hear about oracle machines. They can solve any problem, even the halting problem.

      (It’s just another mathematical construct that you can do cool things with to prove certain things)

      • Julian@lemm.ee
        link
        fedilink
        arrow-up
        5
        ·
        1 year ago

        Thanks for the fun rabbit hole. They can’t really solve the halting problem though, you can make an oracle solve the halting problem for a turning machine but not for itself. Then of course you can make another oracle machine that solves the halting problem for that oracle machine, and so on and so forth, but an oracle machine can never solve its own halting problem.

    • fubo@lemmy.world
      link
      fedilink
      arrow-up
      8
      ·
      1 year ago

      If you augment a TM with nondeterminism, it can still be reduced to a deterministic TM.

    • rockSlayer@lemmy.world
      link
      fedilink
      arrow-up
      6
      ·
      1 year ago

      Nondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.

      • Christian@lemmy.ml
        link
        fedilink
        arrow-up
        1
        ·
        1 year ago

        It’s been a long long time since I touched this but I’m still almost positive deterministic machines can solve everything in NP already.

        • rockSlayer@lemmy.world
          link
          fedilink
          arrow-up
          1
          arrow-down
          1
          ·
          1 year ago

          They exist in the same grammatical hierarchy so theoretically they can solve the same problems. What I should have said was that nondeterministic turing machines can solve NP problems in P