Talk:Nondeterministic algorithm

Untitled

In the intro, "a nondeterministic algorithm is an algorithm with one or more choice points where multiple different continuations are possible". What's a choice point? What's a continuation?

I don't know how to address this comment. If anyone else feels it should be clarified, please do. Rp 16:06, 20 October 2007 (UTC)[reply]

In need of massive work

Wow, there's about 1.2 zillion different types of nondeterministic algorithms (if you include things like stochastic methods, etc). This article is in need of serious attention. Perhaps I'll have to see to that! - 172.133.246.35 06:42, 2 December 2006 (UTC) (JustinWick)[reply]

I think it's better to discuss stochastic methods separately, and link to them here. Rp —Preceding comment was added at 16:02, 20 October 2007 (UTC)[reply]

Is "nondeterministic algorithm" and "probabilistic deterministic algorithm" the same?

In the example "Primality testing" the "Guess an integer..." part of a concrete program/implementation can only use a random number generator to get the job done. Does this mean, that "nondeterministic" and "probabilistic deterministic" are the same in this instance?

It is not the same thing. A probabilistic algorithm is an algorithm in which nondeterminism is resolved by the use of probability. You don't just say that multiple choices are possible, you also give the likelihood for each of the choices to be made. Rp 18:54, 19 October 2007 (UTC)[reply]

I removed another sentence from that example which maintained the suggestion that nondeterminism and random choice are the same. Rp (talk) 20:15, 30 March 2009 (UTC)[reply]

Merge

Can anyone explain why the merge with nondeterminstic programming is a good idea? Or OK if I just remove the merge tags? Sam Staton 16:20, 8 October 2007 (UTC)[reply]

The term "nondeterministic programming" feels like a contradiction to me. We don't usually combine these two words, even though it makes sense to do so. Rp 18:55, 19 October 2007 (UTC)[reply]

I have also read the article. It's too sketchy but it does seem to have merit, as far as I can tell (I am not familiar with the systems mentioned). I think merging it here would be a bad move, because this article is about the idea of a nondeterministic algorithm, which is separate from the idea of actually programming systems in terms of them. Rp 15:59, 20 October 2007 (UTC)[reply]

Reverted edit

I reverted an edit by an anonymous editor. The sentence "A nondeterministic algorithm as an algorithm that, given the same input, may produce different results." is not true: the important thing about a non-deterministic algorithm is that it may make (nondeterministic) choices during execution. Also the first paragraph, even as it stands, is certainly not a "formal definition". If this is unclear, I'm happy to discuss. Sam Staton 10:06, 17 October 2007 (UTC)[reply]

I don't see how the edit being made by an anonymous editor is relevant. That being said, the point of the summery of any article is to make the subject matter approachable.

The 'old summary' is too technical and most definitely not approachable. Considering the old summary to be 99% accurate and completely unapproachable, and considering the new summary to be 80% accurate and totally approachable, I believe the less accurate and approachable definition is the better choice. Wikipedia guidelines also dictate that summaries should be approachable even if they are slightly inaccurate. Users wanting to know more about the subject will continue reading and learn the more correct definition, and people uninterested will leave knowing, for the most part, what they came to learn. If we turn these readers off from reading the article by slapping them across the face with an overly complicated summary, the reader loses and the writer doesn't gain anything.

Your concern about the 'new summary' being inaccurately is unwarranted anyway. Picking apart the word , the inverse of deterministic, yields no importance to making choices. If something is determined then the output has already been decided even before completion. The inverse would be: If something is not determined then the output has not already been decided. There is no implication of choices being made, and if there were and you still think its extremely important, than add that to the simple summary.

I have brought back the simple summary and have fixed a typo in it. I have also renamed the 'formal' definition to 'explicit' definition per your suggestion, which I agree with.

Hello, I think you misunderstood my comment - I don't hold anything against anonymous editors, and I respect your right to anonymity. I just wanted to identify the edit I was talking about.

As I said, it is quite reasonable to ask for a simpler first sentence. But I maintain that your first sentence was far too simple, to the extent that it was wrong. A great many important nondeterminstic algorithms do not return different results for a fixed input. These kinds of algorithms are really important in the study of nondeterminstic polynomial time, in complexity theory. This is one of the main fields of computer science where nondeterminstic algorithms are important. I'm not sure how familiar you are with this.

In line with this, I have tried to correct and improve the opening first sentence. I hope its clearer than the longer paragraph, without being misleading. It's still not perfect, I admit. (In case you find I don't reply to any further discussion: I'll be away now for a few days.) I also changed 'explicit' to 'detailed', since I think that is more appropriate. All the best, Sam Staton 08:42, 18 October 2007 (UTC)[reply]

I do not feel it is appropriate to include the word 'deterministic' in the summary of this article because it goes along the lines of using a a word to describe it self. Again, I stress that explicitly stating that choices are being made isn't necessary. I believe that the word algorithm implies a decision making process is occurring in some fashion.

I don't know whether I understand your objection, and I have no idea how to address it. Can you please suggest a rewording that would be more to your taste? (And sign your comments by appending four tildes.) Thanks. Rp 15:52, 21 October 2007 (UTC)[reply]

This seems to be an old discussion, but I would like to add that perhaps the many nondeterministic algorithms do in fact give the same output given the same input and are neither inherently parallel nor randomized. These include regular expressions, many parsing algorithms, type inference, etc. I don't know of a good definition, but the current one is wrong and misleading. I do not think it is helpful for non-experts. It may even be a good idea to avoid any definition at all in the beginning and introduce the subject via examples or by how nondeterminism is implemented using backtracking on physical computers. Mentioning randomization and parallel implementation of nondeterminism leads to confusion if done too early. The page doesn't go into this, but randomization is most often a sound but not complete implementation of nondeterminism (if it proves something, that proof is correct, but it may not find the proof). Parallelism is better but is misleading since it can conflate potential to be incorrect with nondeterminism. Slaymaker1907 (talk) 09:56, 1 March 2021 (UTC)[reply]

examples

Examples 2-4 leave a reader with no clue why they describe nondeterministic algorithms, each for its own reason I don't even want to start explaining. Is there an expert in the subject who can do a decent job here?

I don't think of merge sort as a nondeterministic algorithm at all. Example #4 is an algorithm, but not for the problem described. I'm a logician though, not a computer scientist, and they are known to be sufficiently bad with they terminology that I am reluctant to edit too much without having reference to a CS text, which I don't. — Carl (CBM · talk) 23:59, 26 April 2010 (UTC)[reply]

I think all the examples on the page are terrible. Can we just delete all of them? None of them seem to exhibit nondeterminism in the sense of nondeterministic Turing machines or a nondeterministic finite-state machine. --Robin (talk) 02:52, 27 April 2010 (UTC)[reply]

I agree with that. My only concern is that maybe the term "nondeterministic algorithm" is used more generally in CS, not just referring to automata. — Carl (CBM · talk) 11:07, 27 April 2010 (UTC)[reply]

I checked the incoming links to the page, and it looks like there are two different meanings of the words "non-determinism" that both link to this page. The first is in the sense of non-deterministic TMs, and the second meaning seems to be anything that is not deterministic (which could mean a random choice, or a choice where the user is not told how the choice is made). This page should probably then reflect these two meanings, or have one of them redirect to a different page. --Robin (talk) 13:06, 27 April 2010 (UTC)[reply]

If you want to write an article about nondeterministic automata, call it Nondeterministic automaton. If you think the examples are wrong, improve them or at least explain what's wrong so it can be fixed by others. Rp (talk) 08:42, 4 May 2010 (UTC)[reply]

I can tell you what I think is wrong: I have never heard the word "nondeterministic algorithm" used to specify an algorithm that is simply underdefined, as in the merge sort example on this article. As far as I can tell, with the way this article uses its terminology, "put the elements in order" is an example of a nondeterministic sort algorithm. Compare the "shopping list" example. It's hard for me to call these "algorithms" in any sense. — Carl (CBM · talk) 11:32, 4 May 2010 (UTC)[reply]

I think you have a point - the term isn't commonly used in such a wide sense. But I can't see how to make a good definition that would exclude such examples. Rp (talk) 07:58, 8 June 2010 (UTC)[reply]

Nondeterministic doesn't mean an algorithm that makes choices

There are many algorithms that may make an arbitrary choice at some point that are not considered nondeterministic by any source I'm aware of. In nearly any search, there is a choice of which node to visit next, but that does not make the search nondeterministic. In quicksort, any element may be chosen as the partition, but that does not make quicksort nondeterministic. According to CLRS, a multithreaded algorithm is nondeterministic if its behavior might vary from run to run. That is, the algorithm makes a choice, and on different runs that choice may differ. In other words, the exact behavior of the algorithm cannot be determined ahead of time. I will rework this article entirely unless someone can come up with a source that contains a different definition. -- Schapel (talk) 17:08, 16 August 2011 (UTC)[reply]

I am not sure if you reworked it but this presentation seems completely wrong. Two of the references get it right with one reference claiming: (A nondeterministic algorithm is) " A conceptual algorithm with more than one allowed step at certain times and which always takes the right or best step. It is not random, as in randomized algorithm, or indeterminate. Rather it has the supercomputational characteristic of choosing the optimal behavior."

Can we please copy that definition. Nondeterministic algorithms don't really have physical counterparts as in algorithms with choice points which choose a progression. Rather, they are used in studies of conceptual algorithms and formal verification. I.e., they are convenient in providing specifications. A (deterministic) sorting algorithm is equivalent to its nondeterministically specified algorithm which simply chooses the right ordered sequence. Typically, a nondeterministic algorithm doesn't have a direct computational interpretation which seems to be the source of all the confusion here. Providing a definition as if it has a computational interpretation completely misses the point.

The introduction is not 80% correct, it is 100% wrong. This article needs a rewrite. 86.82.44.193 (talk) 14:01, 5 July 2015 (UTC)[reply]

This is how it was explained in the formal languages course I took as a student: a nondeterministic algorithm is not an algorithm that makes choices, but one that leaves choices open. It has at least one explicit choice point for which the decision which of the available options to take is left open, i.e. not made by the algorithm, and while running, any of the available options may be taken. It is not the case that the algorithm always magically decides on an optimal choice. 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. As it was explained to me, this is not a property of nondeterministic algorithms as such, but only of how they are applied in defining nondeterministic acceptance of languages. So quicksort in which some choice point, e.g. the choice of how to partition, is left open in this way, is indeed a nondeterministic algorithm. I do agree that it is confusing to mention a sorting algorithm as an example, because the relationship between such an algorithm and its intended results (a sorted input string) is completely different from the relationship between a nondeterministic string accepting algorithm and its intended result (acceptance or nonacceptance of the input string). Rp (talk) 21:10, 6 July 2015 (UTC)[reply]

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. Rp (talk) 21:10, 6 July 2015 (UTC)[reply]

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.86.82.44.193 (talk) 13:57, 7 July 2015 (UTC)[reply]

You got the meaning of "nondeterministic algorithm" completely wrong

In the modern theory of algorithms and complexity theory the term "nondeterministic algorithm" has a very specific meaning. Nondeterministic algorithm are not opposite of deterministic one -- although the way English language works suggests so. Nondeterministic algorithm is nondeterministic in the same way as Non-deterministic_Turing_machine is, and it doesn't make any sense to speak here about "execution" or "state" of such algorithm. Because you don't execute nondeterministic Turing machines in the way you execute Python programs.

A nondeterministic TM can accept or reject an input -- the input is accepted if and only if there is a sequence of nondeterministic choices which can lead to the ACCEPT state of TM. And this definition of nondeterministic TM agrees with the way nondeterministic finite automatons, branching programs, decision trees or circuit are defined. All these different models of computation have deterministic, nondeterministic and probabilistic analogs -- and all of these are examples of nondeterministic algorithms.

You can read more about this for example Arora and Barak's complexity textbook -- http://theory.cs.princeton.edu/complexity/. To summarize, an algorithm can be of these mutually exclusive types:

* Deterministic
* Nondeterministic
* Probabilistic
* …

So nondeterministic algorithms do not include probabilistic ones.

I think the best thing to do with this article is to either just replace it with redirection to the article Non-deterministic_Turing_machine, or to define here what is nondeterminism the way it is done by Arora and Barak, and give further links to articles about nondeterministic TMs, FAs, circuits and so on.

Maybe there are some other fields of CS of which I'm not aware of, and they have their own definition of nondeterminism. In this case this article probably should mention that too, but focus more on the Arora&Barak's definition of nondeterminism -- because this is what they call nondeterminism at any university course on algorithms today. — Preceding unsigned comment added by Ph14nix (talk • contribs) 14:33, 22 October 2019 (UTC)[reply]

I agree that the article is confusing. In fact, its subject is not "nondeterministic algorithm" but "nondeterministic computation". I have added a hatnote for clarifying the subject of the article, and redirecting to Nondeterministic model of computation. However, there was no article of this name, so I have created it as a redirect to Non-deterministic Turing machine. Also, I will request a move of Nondeterministic algorithm to Nondeterministic computation, which was a redirect to Non-deterministic Turing machine (I have just changed the target into Nondeterministic algorithm).

IMO, Nondeterministic model of computation should be expanded into a true article, at least a WP:stub. Are you willing for that? D.Lazard (talk) 17:20, 22 October 2019 (UTC)[reply]

Requested move 22 October 2019

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: No consensus. (non-admin closure) Cwmhiraeth (talk) 14:21, 15 November 2019 (UTC)[reply]

Nondeterministic algorithm → Nondeterministic computation – The present title is clearly ambiguous as shown in the preceding thread of this talk page, and the disambiguation hatnote that I have added to the article. The proposed title is much clearer as referring to effective computation (the subject of the article rather than to abstract algorithms. D.Lazard (talk) 17:36, 22 October 2019 (UTC) --Relisting. Steel1943 (talk) 03:35, 31 October 2019 (UTC) —Relisting. Wug·a·po·des 04:53, 8 November 2019 (UTC)[reply]

Oppose This article is, in its current state, confusing, but the proposed rename won't resolve the confusion. It seems there are at least two kinds of things that are referred to as "Nondeterministic algorithms" in the literature: A) Algorithms written using primitives associated with nondeterministic models of computation/NTMs. This is discussed above by Sam Staton, RobinK, and Ph14nix above, and in this EL (and the NIST EL and the Floyd paper) B) Algorithms whose behaviour might vary from run to run. According to Schapel above, CLRS uses this sense (though they don't indicate whether the work specifically uses the phrase "nondeterministic algorithm"). This other meaning is also alluded to in some other comments above, including a reply from Robink. Right now, this article gives a mish-mash of concepts A and B, which is bad, because they're totally different.

Most of the article's current content, and all its references/external links (except CLRS), relate to meaning A. We also have pretty good evidence that the current title is the WP:COMMONNAME for meaning A. The remnants of B should therefore probably be swept away (possibly into a separate article, if there's enough coverage of it as a distinct concept. Colin M (talk) 00:19, 24 October 2019 (UTC)[reply]

As explained above, for me, meaning A is a subset of meaning B. I agree the two notions should be discussed in separate articles. I'm not sure how best to resolve that. Rp (talk) 17:13, 25 October 2019 (UTC)[reply]

IMO, the solution of the problem is

To make Nondeterministic algorithm a disambiguation page for disambiguating between meanings A and B
To make Nondeterministic model of computation an article for the meaning A (presently, this is a redirect to Nondeterministic Turing machine)
To move, as requested, Nondeterministic algorithm to Nondeterministic computation, and to update it for making clear that it is about meaning B, and that "Nondeterministic algorithm" is often used for this meaning B

This is what I had in mind when I requested this move, except that I thought of leaving a redirect rather than a dab page. I am now convinced that a dab page is better. D.Lazard (talk) 18:10, 25 October 2019 (UTC)[reply]

I'm not convinced at this point that there's enough sourcing for B or enough to say about it to merit a standalone article. The only source that's been mentioned in reference to meaning B is CLRS, and as far as I can tell it could just be a passing mention. (I don't have a copy of CLRS at hand. Perhaps someone who does would be kind enough to do a reference check?) Colin M (talk) 17:10, 26 October 2019 (UTC)[reply]

I don't think it's correct to say that A is a subset of B. There are a few ways to think about the "execution" of a non-determinstic algorithm. We can think of it as...

Running on a non-deterministic computer that "magically" makes the right choice at each branching point.
Making all possible choices at each branching point, along the lines of the powerset construction
Running on a deterministic computer that exhaustively searches the state space via breadth-first search or some other search algorithm

None of these have the property that they "can exhibit different behaviors on different runs for the same input" (unless you deliberately choose a randomized search algorithm for implementation #3 - but this is more like a property of the 'compiler' than the algorithm itself) Colin M (talk) 17:31, 26 October 2019 (UTC)[reply]

Once again: I don't think of the action of a nondeterministic algorithm in any of these three ways, as they make nondeterministic machines very weird creatures. There is a fourth way:

Running on a non-deterministic computer that makes choices at each branching point.

However, we then have to reconsider the notion of acceptance, which no longer means: whatever the outcome of the algorithm's run, that's the result. Instead, we accept nondeterministically, that is to say: we accept a string if some run of the machine accepts it. This interpretation makes physical sense, it directly corresponds to search problems in real life, and it is natural to people who have seen modal or temporal logic (see Possible world). Rp (talk) 08:50, 8 November 2019 (UTC)[reply]

To be clear, when you say it "makes choices", you mean that it makes choices stochastically? If so, that sounds like a very different beast from the other conceptualizations. In particular, it has the property that, if we're doing a finite number of runs, there is a non-zero chance that the algorithm returns the wrong answer (i.e. rejects when it should have accepted). I don't think this agrees with what RS say about randomized algorithms e.g. [1], [2]. Colin M (talk) 20:01, 10 November 2019 (UTC)[reply]

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.

Misleading Article

I think that this page is misleading. A nondeterministic algorithm makes a choice as part of its computation. Making a choice, to me, implies free will. Many seem to call any algorithm which produces a difficult-to-predict output a "nondeterministic algorithm". However, the real reason why the algorithm doesn't have the same predictable outcome is because the entire input state space was not taken into account. This includes what's exactly in all of your system memory, state of all CPU cores, temperature, environmental radiation, etc. Taking all of those things into account, I bet you that your "nondeterministic algorithm" is only a simulation of one. This is also touched upon by other commenters above to some extent. 02Tails (talk) 00:37, 31 May 2021 (UTC)[reply]

It is a fact that different people use "nondeterministic" with different meanings. Wikipedia cannot do anything against that. What Wikipedia can do is to make clear the difference between different meanings. The hatnote at the top of the article is there for this reason. It would probably better to expand it into a detailed explanation in the article.

This being said the article is effectively confusing in its present state. It suffices to read this talk page, and specially the discussion on the requested move to see that there is a consensus about that. The problem is that there is no consensus about the way of solving the problem. Can you propose something? D.Lazard (talk) 08:04, 31 May 2021 (UTC)[reply]

I appreciate the hatnote. It adds value in directing the reader to more formal documentation. What I'd like to see here is the summary paired down to the effect of "a nondeterministic algorithm is one that makes a choice". Then further down in the article, we can discuss what it means to make a choice i.e. spontaneous vs stochastic. I'm willing to concede that calling an algorithm "nondeterministic" in theoretical settings means something different from practical settings. That line needs to be drawn somewhere so the reader coming from either setting won't be confused. We can't define things absolutely here when there is a gray area to think about. 02Tails (talk) 16:31, 31 May 2021 (UTC)[reply]

It's exactly the opposite: a nondeterministic algorithm leaves choices open, it refrains from making them. Or in the context of nondeterministic acceptance, you could say: it makes all of them. What it doesn't do is make choices, i.e. choose between multiple options by picking one and not picking the rest. Rp (talk) 21:43, 1 June 2021 (UTC)[reply]

I wouldn't say "exactly" the opposite, but you're right. I didn't word that carefully enough. My point was that however it is defined, it is important to also explain what you mean by "choice".02Tails (talk) 23:52, 26 July 2021 (UTC)[reply]

The biggest problem is that the hatnote promises that the article is about meaning B (as defined in #Requested move 22 October 2019), but that is only true of the lead, and the rest of the article is about meaning A. I am adding a "Confusing" template to warn readers of the article.
One solution would be to split this article. The two articles would need different names. I suspect that "nondeterministic algorithm" is more appropriate for meaning A. Partly because Floyd (1967) uses it with meaning A, but also because "nondeterminism" with meaning B is only desirable in special cases with more specific names such as randomized algorithm.
An alternative solution is to merge the material into other articles. There are a lot of possibilities. Those for meaning A include nondeterministic programming and nondeterministic finite automaton. Those for meaning B include deterministic algorithm, concurrent computing and concurrency control. For disambiguation there is indeterminacy in computation. JonH (talk) 16:11, 30 January 2022 (UTC)[reply]

I agree with the confusing tag, but I disagree with the suggested solution. This article is essentially a stub, and is awfully written. Although short, it is full of incorrect or approximate statements. So, the first thing to do is to rewrite it completely, with a section for each sort of nondeterminism (concurrent programming, random choices, nondeterminism of the output vs. nondeterminism of the computational path for a determinisitic output, etc.). One may add a section on nondeterministic models of computation, for showing that it models nondeterminism and parallelism in some non-realistic way (this is non-realistic in the sense no choice is done, and the computation stops when the fastest of all possible choices is finished). The computational complexity of non-deterministic algorithms must also be considered (in general the average complexity, which has nothing to do with any nondeterministic complexity).

It is only when the article will describe well its subject that a discussion on the structure of the related articles could be useful. D.Lazard (talk) 17:29, 30 January 2022 (UTC)[reply]

I suspect that the source of the confusion in discussing non-deterministic algorithms indeed arises from the use of "choice" in its apparent definition. However when looked at mathematically a Non-Deterministic Algorithm might be making an infinite number of choices, as it could contain infinite paths. "Infinite choices" is mathematically modeled by the Axiom of Choice in ZF Set Theory, in this context probably a special case like "Countable Dependent Choice".

So when discussing a "paper and pencil" formulation of a non-deterministic algorithm indeed it can take the many (or conceptually infinite) choices that it needs to. This is reasoned about using "Konig's Lemma" in places such as the powerset construction and elsewhere. However the Axiom of Choice is non-constructive and should not be used in a mechanical setting (without explanation, at least). But Konig's lemma fails in the mechanical setting. Indeed it fails in a recursive setting (Kleene's singular Tree theorem) resulting in an axiom system known as WKL, which extends recursion theory a little.

Thus mechanical Non-Deterministic Algorithms will not behave as expected, and not behave as their "paper and pencil" counterparts.

Unitl this theory is explained there will be controversies over the term Non-Deterministic Algorithms. RoyMWiki (talk) 16:08, 16 April 2023 (UTC)[reply]

Isn't that the point of artificial intelligence? We are literally trying to build systems where this is the case. From a practical standpoint there are "non-deterministic" systems out there which are outside of the control of the testing party, sure they could be deterministic if you got super scientific with it but to what extent is that practical vs just saying "its non deterministic". I'm sure we could invest enough to prove everything is in-fact deterministic but it would be quite expensive and impractical and what's the point? Just my 2 cents as an engineer working on systems like this every day. 172.58.255.84 (talk) 22:02, 5 March 2024 (UTC)[reply]

I have rewritten the article to emphasize the commonality and differences between the different uses of nondeterminism, following Lazard's suggestion "It would probably better to expand it into a detailed explanation in the article." As for the philosophical questions about AI and free will, there may be a connection but I don't think this article is the place for them. —David Eppstein (talk) 06:31, 7 July 2024 (UTC)[reply]

This is much better. Previously, having read this talk page and Hehner (Logic of Programming, 1984, page 118), I believed that the word “nondeterminism” is used in computer science with various incompatible meanings. So I thought trying to cover them all in an introduction was a bad idea. But having read this new version of the article, I now understand. Thanks.

I have a constructive suggestion for consideration. This article could be renamed from "Nondeterministic algorithm" to "Nondeterminism" with just a small change to the first sentence. At present, nondeterminism is a disambiguation page, and a reader who wants to learn about nondeterminism is presented with a list of 5 articles (including this one). Depending on the order in which they read the articles, they may become confused. They would be better off reading this article first. JonH (talk) 16:01, 7 July 2024 (UTC)[reply]