coja@lemmy.ml to Programmer Humor@lemmy.ml · 2 years agoEarly disappointmentlemmy.mlimagemessage-square36fedilinkarrow-up1753arrow-down114
arrow-up1739arrow-down1imageEarly disappointmentlemmy.mlcoja@lemmy.ml to Programmer Humor@lemmy.ml · 2 years agomessage-square36fedilink
minus-squareargv_minus_one@beehaw.orglinkfedilinkarrow-up4arrow-down3·2 years agoSince when were Turing machines ever nondeterministic?
minus-squaregaryyo@lemmy.worldlinkfedilinkarrow-up8arrow-down1·2 years agoWait 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)
minus-squarefubo@lemmy.worldlinkfedilinkarrow-up6·2 years agoIf you augment a TM with nondeterminism, it can still be reduced to a deterministic TM.
minus-squarerockSlayer@lemmy.worldlinkfedilinkarrow-up5arrow-down2·2 years agoNondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.
minus-squareChristian@lemmy.mllinkfedilinkarrow-up1·2 years agoIt’s been a long long time since I touched this but I’m still almost positive deterministic machines can solve everything in NP already.
minus-squarerockSlayer@lemmy.worldlinkfedilinkarrow-up1arrow-down1·2 years agoThey 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
Since when were Turing machines ever nondeterministic?
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)
If you augment a TM with nondeterminism, it can still be reduced to a deterministic TM.
Nondeterministic turing machines are the same kind of impossible theoretical automaton as an NFA. They can theoretically solve NP problems.
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.
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