this post was submitted on 19 Jul 2023
1042 points (98.2% liked)

Programmer Humor

32380 readers
425 users here now

Post funny things about programming here! (Or just rant about your favourite programming language.)

Rules:

founded 5 years ago
MODERATORS
 
you are viewing a single comment's thread
view the rest of the comments
[–] argv_minus_one@beehaw.org 2 points 1 year ago (3 children)

Since when were Turing machines ever nondeterministic?

[–] garyyo@lemmy.world 14 points 1 year ago (1 children)

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)

[–] julianh@lemm.ee 5 points 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 8 points 1 year ago

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

[–] rockSlayer@lemmy.world 4 points 1 year ago (1 children)

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

[–] christian@lemmy.ml 1 points 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.