This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
|
This article was the subject of a Wiki Education Foundation-supported course assignment, between 25 August 2020 and 10 December 2020. Further details are available on the course page. Student editor(s): Kaileesmyth.
Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT ( talk) 20:16, 16 January 2022 (UTC)
There are a Effective method that is not a Algorithm? —Preceding unsigned comment added by 187.39.184.57 ( talk) 12:54, 8 May 2010 (UTC)
--The article is not too good. The notion of method is so general that it can include any . . . well . . . what . . . behavior, activity, sequence of motion . . . of any sort whatever. This includes behaviors or activities with natures that we call analog, digital (computation, calculation), random, metaphysical i.e. prayer (every time I pray to X I get Y), or oracular, i.e. "appealing to [make-believe] oracles" (oracles being important for theory of computability). If it works -- no matter how weird or intuitive or fictional it may be -- it's effective: it meets the metamathematical goal -- the specification, the intent/desires. Bill Wvbailey ( talk) 22:48, 12 October 2011 (UTC)
The second to last paragraph reads: A further elucidation of the term "effective method" may include the requirement that, when given a problem from outside the class for which the method is effective, the method may halt or loop forever without halting, but must not return a result as if it were the answer to the problem.
I doubt that this particular statement is compatible with the current understanding of what a computable function is. Not only is there no citation or reasoning given, but I can even remember quite a few proofs making explicit use of the fact that the result of an algorithm does not matter when invoked on an input from outside its domain (look at it as a function and the input as either in the domain of this function or not). As an example, consider the Choice operator, which, given a non-empty boolean predicate f, returns some value y for which this predicate is true; that is: \forall f. ( (\exist x. (f x)) => ( Choice(f) = y such that (f y) = T ) ) (unfortunately I couldn't come up with a link to a canonical definition, but they should, hopefully, all go along these lines). The definition does not require any behaviour for empty predicates - and in fact, some interpretations (that is, models for the operator) treat it as returning an arbitrary value if there is no value fulfilling f. As a side-effect, in such models the existence quantifier can be conveniently expressed as \exist == \lambda f. f( Choice(f) ) . Of course, if that behaviour is desired, one would extend the domain of Choice on all predicates; but generally, this is not done, and the behaviour is not specified.
Since I obviously couldn't come up with a source for my claim right now either, I would appreciate some comment from the wikiprojects computational theory / logic / mathematics or the like. If no one can comment on it, I'll go plow through the library, but that could take a while. It doesn't look like such a big thing as if it was worth such an effort. Se'taan ( talk) 07:41, 28 December 2012 (UTC)
*Comment on RFC: Without prejudice to the logical content of the article plus this section of the talk page, I suggest that if there is room for questions of this nature, then that suggests that readers might reasonably be caught short and do some head scratching on the subject, whether the formal nature of the subject and the description have covered the relevant points of incomprehension or not. In such cases in an encyclopaedia it is at the very least desirable if practical to cover such points in such a manner that a reasonably intellectually equipped and educated reader could be expected to work it out on the basis of the material supplied. Since all parties so far contributing to this exchange seem to be reasonably willing to eliminate difficulties or shortcomings in the article, I suggest that a good approach might be to cooperate on collecting perceived points of difficulty in an explicit list, rather than an unstructured exchange. If we can achieve that, then it should be manageable to construct a moderately comprehensible and compact expansion to the article' s text to eliminate perceived shortcomings. I also have put a bit of handwaving into the preceding section, though I am not confident that in its present form it would be useful in this connection. Anyone working on the problem however is welcome to it in part or in whole or variously processed. JonRichfield ( talk) 09:08, 9 January 2013 (UTC)
Not being a math geek, I fail to see any notability behind the article's title. Is "effective method" really a phrase that means "an algorithm that does this thing that we can't quite agree on" and nothing else? In my opinion this article isn't very effective without more reliable sources. Krushia ( talk) 04:53, 31 December 2012 (UTC)
This is an outdated terminology. The references are either old and historical or obscure. No one uses it anymore. The terminology in the article is also nonstandard. It is more confusing than helpful. I think it should be deleted. There is no need for his article. 24.212.193.99 ( talk) 17:25, 7 September 2014 (UTC)
The very last sentence restricts the Church-Turing thesis on number-theoretic functions, i.e. any number-theoretic function that is effectively calculable is recursively computable. I think the restriction on number-theoretic functions might be unnecessary. Here's my reasoning:
1) Possible real-world difference of effective calculability and number-theoretic functions: It's open whether some form of hypercomputation can exist that were stronger than discrete symbolic (i.e. digital) computation, which includes numeric computation. If yes, then the Church-Turing thesis would make a statement about that hypercompuation, too. These forms of hypercomputation might be impossible to represent with number-theoretic functions, but would obviously be an effective method for computing something. In a nutshell: There could really be functions that are not number-theoretic and for which an effective method exists, and that would turn the Church-Turing thesis wrong (as I read the thesis...). The article would reflects this only if we discard "number-theoretic".
2) Possible model with difference between symbolic discrete values and numbers: Even if there is no super-Turing computation, could there be a model (or "interpretation") of reasoning (or "theory" as in model theory) in which symbolic reasoning cannot be fully emulated with numerical reasoning? If such a (consistent, non-trivial) model exists, and if it contains all structures necessary for stating the Church-Turing thesis, then the Church Turing thesis should (?) be wrong in that model. Again, this is holds only when we do not restrict functions to be "number-theoretic".
Since this reasoning is somewhat vague, touches mainly philosophical aspects, and I'm not a philosopher, I'm not going to change this unless given qualified support. I'm going to ask for help on Talk:Church-Turing thesis, though -- Se'taan ( talk) 23:07, 29 September 2013 (UTC)
Is almost surely halting good enough to satisfy our definition of an effective method?
Classical (not quantum) bogosort, which almost surely halts, is conventionally classified as a sorting algorithm, which depends on the definition of an algorithm and thus an effective method. To what extent is this valid? -- SoledadKabocha ( talk) 19:06, 3 November 2015 (UTC)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
|
This article was the subject of a Wiki Education Foundation-supported course assignment, between 25 August 2020 and 10 December 2020. Further details are available on the course page. Student editor(s): Kaileesmyth.
Above undated message substituted from Template:Dashboard.wikiedu.org assignment by PrimeBOT ( talk) 20:16, 16 January 2022 (UTC)
There are a Effective method that is not a Algorithm? —Preceding unsigned comment added by 187.39.184.57 ( talk) 12:54, 8 May 2010 (UTC)
--The article is not too good. The notion of method is so general that it can include any . . . well . . . what . . . behavior, activity, sequence of motion . . . of any sort whatever. This includes behaviors or activities with natures that we call analog, digital (computation, calculation), random, metaphysical i.e. prayer (every time I pray to X I get Y), or oracular, i.e. "appealing to [make-believe] oracles" (oracles being important for theory of computability). If it works -- no matter how weird or intuitive or fictional it may be -- it's effective: it meets the metamathematical goal -- the specification, the intent/desires. Bill Wvbailey ( talk) 22:48, 12 October 2011 (UTC)
The second to last paragraph reads: A further elucidation of the term "effective method" may include the requirement that, when given a problem from outside the class for which the method is effective, the method may halt or loop forever without halting, but must not return a result as if it were the answer to the problem.
I doubt that this particular statement is compatible with the current understanding of what a computable function is. Not only is there no citation or reasoning given, but I can even remember quite a few proofs making explicit use of the fact that the result of an algorithm does not matter when invoked on an input from outside its domain (look at it as a function and the input as either in the domain of this function or not). As an example, consider the Choice operator, which, given a non-empty boolean predicate f, returns some value y for which this predicate is true; that is: \forall f. ( (\exist x. (f x)) => ( Choice(f) = y such that (f y) = T ) ) (unfortunately I couldn't come up with a link to a canonical definition, but they should, hopefully, all go along these lines). The definition does not require any behaviour for empty predicates - and in fact, some interpretations (that is, models for the operator) treat it as returning an arbitrary value if there is no value fulfilling f. As a side-effect, in such models the existence quantifier can be conveniently expressed as \exist == \lambda f. f( Choice(f) ) . Of course, if that behaviour is desired, one would extend the domain of Choice on all predicates; but generally, this is not done, and the behaviour is not specified.
Since I obviously couldn't come up with a source for my claim right now either, I would appreciate some comment from the wikiprojects computational theory / logic / mathematics or the like. If no one can comment on it, I'll go plow through the library, but that could take a while. It doesn't look like such a big thing as if it was worth such an effort. Se'taan ( talk) 07:41, 28 December 2012 (UTC)
*Comment on RFC: Without prejudice to the logical content of the article plus this section of the talk page, I suggest that if there is room for questions of this nature, then that suggests that readers might reasonably be caught short and do some head scratching on the subject, whether the formal nature of the subject and the description have covered the relevant points of incomprehension or not. In such cases in an encyclopaedia it is at the very least desirable if practical to cover such points in such a manner that a reasonably intellectually equipped and educated reader could be expected to work it out on the basis of the material supplied. Since all parties so far contributing to this exchange seem to be reasonably willing to eliminate difficulties or shortcomings in the article, I suggest that a good approach might be to cooperate on collecting perceived points of difficulty in an explicit list, rather than an unstructured exchange. If we can achieve that, then it should be manageable to construct a moderately comprehensible and compact expansion to the article' s text to eliminate perceived shortcomings. I also have put a bit of handwaving into the preceding section, though I am not confident that in its present form it would be useful in this connection. Anyone working on the problem however is welcome to it in part or in whole or variously processed. JonRichfield ( talk) 09:08, 9 January 2013 (UTC)
Not being a math geek, I fail to see any notability behind the article's title. Is "effective method" really a phrase that means "an algorithm that does this thing that we can't quite agree on" and nothing else? In my opinion this article isn't very effective without more reliable sources. Krushia ( talk) 04:53, 31 December 2012 (UTC)
This is an outdated terminology. The references are either old and historical or obscure. No one uses it anymore. The terminology in the article is also nonstandard. It is more confusing than helpful. I think it should be deleted. There is no need for his article. 24.212.193.99 ( talk) 17:25, 7 September 2014 (UTC)
The very last sentence restricts the Church-Turing thesis on number-theoretic functions, i.e. any number-theoretic function that is effectively calculable is recursively computable. I think the restriction on number-theoretic functions might be unnecessary. Here's my reasoning:
1) Possible real-world difference of effective calculability and number-theoretic functions: It's open whether some form of hypercomputation can exist that were stronger than discrete symbolic (i.e. digital) computation, which includes numeric computation. If yes, then the Church-Turing thesis would make a statement about that hypercompuation, too. These forms of hypercomputation might be impossible to represent with number-theoretic functions, but would obviously be an effective method for computing something. In a nutshell: There could really be functions that are not number-theoretic and for which an effective method exists, and that would turn the Church-Turing thesis wrong (as I read the thesis...). The article would reflects this only if we discard "number-theoretic".
2) Possible model with difference between symbolic discrete values and numbers: Even if there is no super-Turing computation, could there be a model (or "interpretation") of reasoning (or "theory" as in model theory) in which symbolic reasoning cannot be fully emulated with numerical reasoning? If such a (consistent, non-trivial) model exists, and if it contains all structures necessary for stating the Church-Turing thesis, then the Church Turing thesis should (?) be wrong in that model. Again, this is holds only when we do not restrict functions to be "number-theoretic".
Since this reasoning is somewhat vague, touches mainly philosophical aspects, and I'm not a philosopher, I'm not going to change this unless given qualified support. I'm going to ask for help on Talk:Church-Turing thesis, though -- Se'taan ( talk) 23:07, 29 September 2013 (UTC)
Is almost surely halting good enough to satisfy our definition of an effective method?
Classical (not quantum) bogosort, which almost surely halts, is conventionally classified as a sorting algorithm, which depends on the definition of an algorithm and thus an effective method. To what extent is this valid? -- SoledadKabocha ( talk) 19:06, 3 November 2015 (UTC)