Post funny things about programming here! (Or just rant about your favourite programming language.)
Hm, I wonder if I could make these students more miserable by introducing a CPU that permits static operation, then clocking that with a true random number generator?
So now it has output that is deterministic from the standpoint of the CPU but nondeterministic to an outside observer. Probably wouldn't affect the O(n) notation though, come to think of it. It would be funny though.
My favorite subject!
Since when were Turing machines ever nondeterministic?
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