Content deleted Content added
→Misleading Article: thanks and suggestion for article move Tag: Disambiguation links added |
|||
| (28 intermediate revisions by 15 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=Mid}}
}}
==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. [[User:Rp|Rp]] 16:06, 20 October 2007 (UTC)
Line 41 ⟶ 45:
:::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. [[User:Rp|Rp]] 15:52, 21 October 2007 (UTC)
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. [[User:Slaymaker1907|Slaymaker1907]] ([[User talk:Slaymaker1907|talk]]) 09:56, 1 March 2021 (UTC)
== examples ==
Line 105 ⟶ 111:
== Requested move 22 October 2019 ==
<div class="boilerplate" style="background-color: #efe; margin: 0; padding: 0 10px 0 10px; border: 1px dotted #aaa;"><!-- Template:RM top -->
:''The following is a closed discussion of a [[Wikipedia:Requested moves|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a [[Wikipedia:move review|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.''' <small>([[Wikipedia:Requested moves/Closing instructions#Non-admin closure|non-admin closure]])</small> [[User:Cwmhiraeth|Cwmhiraeth]] ([[User talk:Cwmhiraeth|talk]]) 14:21, 15 November 2019 (UTC)
[[:Nondeterministic algorithm]] → {{no redirect|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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:36, 22 October 2019 (UTC)▼
----
▲[[:Nondeterministic algorithm]] → {{no redirect|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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:36, 22 October 2019 (UTC) <small>--'''''Relisting.''''' [[User:Steel1943|<span style="color: #2F4F4F;">'''''Steel1943'''''</span>]] ([[User talk:Steel1943|talk]]) 03:35, 31 October 2019 (UTC)</small> <small>—'''''Relisting.''''' [[User:Wugapodes|Wug·]][[User talk:Wugapodes|a·po·des]] 04:53, 8 November 2019 (UTC)</small>
*'''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 model of computation|nondeterministic models of computation]]/NTMs. This is discussed above by Sam Staton, RobinK, and Ph14nix above, and in [https://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html 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. [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 00:19, 24 October 2019 (UTC)
:: 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. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 17:13, 25 October 2019 (UTC)
:::IMO, the solution of the problem is
:::*To make [[Nondeterministic algorithm]] a disambiguation page for disambiguating between meanings A and B
:::*To make {{noredirect|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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 18:10, 25 October 2019 (UTC)
::::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?) [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 17:10, 26 October 2019 (UTC)
:::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) [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 17:31, 26 October 2019 (UTC)
::::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]]). [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 08:50, 8 November 2019 (UTC)
:::::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. [https://xlinux.nist.gov/dads/HTML/nondetermAlgo.html], [https://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html]. [[User:Colin M|Colin M]] ([[User talk:Colin M|talk]]) 20:01, 10 November 2019 (UTC)
----
:''The above discussion is preserved as an archive of a [[Wikipedia:Requested moves|requested move]]. <b style="color:red">Please do not modify it.</b> Subsequent comments should be made in a new section on this [[Help:Using talk pages|talk page]] or in a [[Wikipedia:Move review|move review]]. No further edits should be made to this section.''<!-- Template:RM bottom --></div>
==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. [[User:02Tails|02Tails]] ([[User talk:02Tails|talk]]) 00:37, 31 May 2021 (UTC)
: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? [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 08:04, 31 May 2021 (UTC)
::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. [[User:02Tails|02Tails]] ([[User talk:02Tails|talk]]) 16:31, 31 May 2021 (UTC)
:::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. [[User:Rp|Rp]] ([[User talk:Rp|talk]]) 21:43, 1 June 2021 (UTC)
::::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".[[User:02Tails|02Tails]] ([[User talk:02Tails|talk]]) 23:52, 26 July 2021 (UTC)
*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]]. [[User:JonH|JonH]] ([[User talk:JonH|talk]]) 16:11, 30 January 2022 (UTC)
::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. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:29, 30 January 2022 (UTC)
: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. [[User:RoyMWiki|RoyMWiki]] ([[User talk:RoyMWiki|talk]]) 16:08, 16 April 2023 (UTC)
::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. [[Special:Contributions/172.58.255.84|172.58.255.84]] ([[User talk:172.58.255.84|talk]]) 22:02, 5 March 2024 (UTC)
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. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 06:31, 7 July 2024 (UTC)
: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. [[User:JonH|JonH]] ([[User talk:JonH|talk]]) 16:01, 7 July 2024 (UTC)
| |||