Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It doesn't help that CS students will potentially end up hearing the term "nondeterminism" to mean different things in different contexts. In the context of the linked repo, it's used in the way they'll probably encounter it when learning about Turing machines, but in less formal contexts it also gets used a lot to describe stuff like "Heisenbugs" where running something more than once doesn't necessarily end up in the same result


> but in less formal contexts it also gets used a lot to describe stuff like "Heisenbugs"

There are pretty formal contexts in which it also means things like that! It's not about formalism, it's just about context.


For me, the idea of nondeterminism was around a computation tree who's branches correspond to possible states of computation.

In the context of a deterministic vs nondeterministic finite automata, a DFA has a linear computation path from the root to an accept/reject state and a NFA branches on epsilon transitions, continuing each potential computation (the "guesses") in so called "parallel universes" until one branch hits an accept state.

This definition follows with Introduction to the Theory of Computation 3rd edition by Sipser (would recommend)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: