Content deleted Content added
→Misleading Article: comments |
→Misleading Article: Reply |
||
Line 151:
::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)
| |||