|
|
|
|
|
|
by nyssos
870 days ago
|
|
|
> Nondeterministic Finite Automata. The "Nondeterministic" in NFA means its transition function goes from states to sets of states, instead of from states to states. Informally, it can explore multiple paths in parallel for the cost of one. They're not probabilistic. |
|
|
Thus, this semantics implicitly encodes the notion that the machine is nondeterministically choosing the next state in each execution.
The decision problem of whether an NFA accepts a string w is what allows for the informal parallel interpretation, that it accepts iff you imagine the computation is forking off a new thread at each nondeterministic branch. But to say that this not nondeterministic or not probabilistic is like saying the Many-Worlds Interpretation means there is no real superposition, or something like that. It's like saying a throw of a dice does not really involve probability because of a symmetry argument that a dice has six equal sides. Mainly, I don't understand that, because I see probability as a way to implement nondeterminism: a system is probabilistic only because it is making nondeterministic choices according to some probability distribution. And checking Sipser 2nd ed. p.368: "A probabilistic Turing machine is a type of nondeterministic Turing machine in which each step is a coin-flip step".
Anyhow, my main issue was that the original commenter casually claimed that probability makes things (physics) uncomputable. But Turing computability has nothing to do with probability, since as I recall the closest concept is the Non-deterministic Turing Machine (NDTM) and with that it is a basic proof to show that NFAs vs. DFAs, as well as NDTMs vs. DTMs, are computationally equivalent and there are theorems for that.
Meaning either they are using an idiosyncratic definition of computability or are ignorant of an introductory course on theory of computing which explains formally what Turing/Church's theories were about when clarifying the concept of computability. Okay or maybe they have a deeper philosophical disagreement with computability and complexity theorists - maybe they reject Sipser's definition above - but these are standard undergraduate curricula in CS by now and it could be argued that perhaps it is the non-CS experts who haven't thought deeply enough about what computability really is and would benefit from actually learning from these subdisciplines. I don't know, as they did not reply.