Content deleted Content added
m h- |
|||
Line 73:
* I don't think the above descriptions are improvements. Calling the options at a choice point "steps" is confusing to me because it suggests to me that they are made in sequence instead of being alternatives. Saying that "on different runs the choices made may differ" is correct but not strong enough: it is essential that whenever a choice is left open, ''any'' of the available options can be taken during a run. Saying that a deterministic sorting algorithm "simply chooses the right sorting sequence" or that a nondeterministic algorithm doesn't have a direct computational algorithm doesn't make sense to me. Providing a definition as if it has ''no'' computational interpretation would completely miss the point! It would suggest that nondeterministic algorithms somehow can't be executed by machines, when the whole point is that they can be. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 21:10, 6 July 2015 (UTC)
* I disagree with how it was presented to you during your studies. "Now a string is said to be accepted by a nondeterministic algorithm or device if there is at least one possible run, i.e. at least one particular set of choices for every choice point encountered during runs, such that the final result is to accept the string." This is (near) correct. A nondeterministic machine accepts a string if it accepts it along one of its execution paths. I find you still give it too much of a computational characteristic in your other treatment.
* Your example regarding sorting doesn't express the 'power' of nondeterministic algorithms as the nondeterministic quicksort algorithm just leaves open a 'probabilistic' choice. I can give a nondeterministic algorithm which will nondeterministically choose a sequence and check all original elements occur and are sorted. That shows the fundamental difference between nondeterminism and determinism whereas your example does not.
* I think I said there is no 'direct' executionable interpretation for nondeterministic algorithms. I agree it's easy to miss the emphasis on 'direct'. Of course there are, if you accept possible exponential blowup. Which is another problem with your example, it doesn't provide insight in why nondeterministic algorithms can only be 'exponentially' simulated (P=NP?). Your example insists on the view that nondeterministic algorithms are a simple variant of deterministic programming with choices left open which can be simulated by choosing _any_ execution path whereas it is about _all_ execution paths.
* I agree that formally nondeterministic algorithms don't leave choices open. But the definition given on the other site is an 80% correct explanation whereas the introduction, I remain, now still is 100% wrong.[[Special:Contributions/86.82.44.193|86.82.44.193]] ([[User talk:86.82.44.193|talk]]) 13:57, 7 July 2015 (UTC)
| |||