Talk:Effective method

Wiki Education Foundation-supported course assignment

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)

Please add example

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)

According to the generally accepted Church-Turing thesis, the answer is no. 67.117.130.143 (talk) 19:46, 12 December 2010 (UTC)

Church-Turing thesis unnecessary. These are synonyms. The Church-Turing thesis is that any effective method / algorithm can be implemented by a Turing machine / Lambda-calculus term. I second the merge proposal. AmirOnWiki (talk) 16:40, 12 October 2011 (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)

As I read the article, plus the article on algorithm, there is indeed a distinction between an effective method and an algorithm. One could for example demonstrate that there is an effective mechanism for a given task (purely for illustration, let us say using trial and error to fit polyominoes into a given knapsack, when it is known that they have come out of that knapsack, and is not known how much spare space, if any, there had been before they had been emptied out). Having done so, it does not follow that any algorithm, let alone a most efficient algorithm had been demonstrated or designed. If the algorithm had indeed been designed, it would have followed that it could be directly translated into a computer program, given the necessary primitive operations and resources of space and processing power, none of which are conceptually requisite to demonstrate the existence of an effective method in principle. Also, it often is quite possible to construct many algorithms to implement a given effective method. JonRichfield (talk) 08:44, 9 January 2013 (UTC)

It's an open question whether a real world example exists. For reference, take a look at Church–Turing thesis#Philosophical implications, particularly "2." and "3.". You might also want to look at Supertask#Super_Turing_machines, Super-recursive_algorithm, Hypercomputer and Digital_physics#The Church–Turing (Deutsch) thesis. I think some related stuff was also in Chaitin's_constant, I just can't recall where exactly in that article. Anyway, if we had such an example of an effective method that was indeed realizable in the real world, we would have refuted the Church-Turing thesis – which is an open question (but generally considered impossible, see the article). Se'taan (talk) 05:00, 23 March 2013 (UTC)

Behaviour for problems from outside the domain

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)

An effective method is a more general concept than a computable function, or an algorithm. It is not solely a concept within math or computers, but is applicable to logical questions in general. The quoted material you are calling into question specifically says "may include." So it certainly doesn't negate uses of the term that do not include. Greg Bard (talk) 08:44, 28 December 2012 (UTC)

On my opinion, the point is that the contraposition of this proposition is that if the method returned a result "as if it were the answer to the problem", then we should conclude that the given problem is NOT "outside the class for which the method is effective" (despite the fact that the method might not do what one expects it to do). -- 213.189.160.119 (talk) 11:21, 28 December 2012 (UTC)

No, it may give an answer and the person constructing the effective method may not realize that the answer is, in fact, wrong. The problem may be outside the class for which the method is effective, and yet fool its constructor into thinking it is effective by the fact the the method gives an answer. In other words, you don't get any points for giving wrong answers. Greg Bard (talk) 11:42, 28 December 2012 (UTC)

Gregbard and IP, thanks for your posts and sorry for my late reply, I had an involuntary wikibreak. Regarding Gregbards first comment: I understood the quoted material as if stating a requirement that would anyway be implicitly resulting from the definition. If that were true, it would exclude the mentioned functions from being effectively computable - and that's why I contested it. I'm aware that 'effective method' is a term used in logics in general, that's why I also asked for comments from the philosophy/logics project.

If you agree that the requirement is purely optional, I'd be perfectly content with reformulating the quoted lines to say so.

Why is any "reformulation" is needed at all? 'A further elucidation of the term "effective method" may include' is perfectly clear. It already says that it is talking about "further elucidations." It already says "may include." "May" means, "optional." So I really am not seeing the problem here. Greg Bard (talk) 05:50, 9 January 2013 (UTC)

Regarding the latter two posts - look at it this way: Every method that always returns an answer is an effective method for some problem. It may, however, not be an effective method for the problem you thought it were (i.e. you were "constructing" it for, if you believe in (pre-)intuitionism). I think Gregbards second post says basically the same. Anyway, that's already beyond my rfc/question, so I'm not going into this. Any objections to me changing those lines? Se'taan (talk) 05:26, 9 January 2013 (UTC)

Again, I'm not seeing the problem. However, I'm open-minded to reformulations that preserve the essential meaning. Greg Bard (talk) 05:50, 9 January 2013 (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)

Notability

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)

I have provided an additional reference just for your benefit. Greg Bard (talk) 05:20, 31 December 2012 (UTC)

Not having seen this page before, I have just added a remark at the end of the first section of this talk page. I hope that it is sufficiently clear.JonRichfield (talk) 08:47, 9 January 2013 (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)

Well, effective descriptive set theory and effective Polish space both have the word effective in it. I assume it means the same thing, as the "effective" being described in this article. So it would seem to be in current usage... ? 67.198.37.16 (talk) 01:29, 29 November 2023 (UTC)

Is the Church-Turing thesis restricted to number-theoretic functions?

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)

The thesis is trivially false without the restriction to number-theoretic functions, because the formal definition of "computable function" only includes number-theoretic functions. (The same issue happens if you define computability to use functions that that a finite binary string and return a finite binary string).

A non-number-theoretic function cannot be computable in that formal sense, regardless whether the function is effectively calculable in some other sense. For example, the function "given one of my shoes, walk into my closet, get the matching shoe, and bring it back" is effectively calculable in some sense, but there is no chance that it is going to be computable by a Turing machine, because Turing machines cannot fetch. That example may seem remote, but for example the Church-Turing thesis also says nothing about analog computability. It only compares the number-theoretic functions algorithmically computable by a human with the number theoretic functions computable by a Turing machine. — Carl (CBM · talk) 14:13, 22 November 2013 (UTC)

Almost surely halting

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)

Classical computability is entirely deterministic. So, even before you run into the question about the fact that the algorithm for bogosort doesn't always halt, there is the deeper question that there is no deterministic way for a human to simulate the algorithm with only pencil and paper, without an additional source of randomness. So the bogosort algorithm is not an effective method in the sense of classical computability. This is OK, because that definition is not trying to capture everything that could possibly be computed, only the things that could be computed deterministically by a human with unlimited time, pencil, and paper. — Carl (CBM · talk) 20:19, 3 November 2015 (UTC)

However, if we treat bogosort as an algorithm that takes a finite list to sort and also an infinite oracle to query for "random" bits, then the resulting oracle computation is effective in the classical sense. It will not halt for every oracle, but it will halt for many of them. In this way, the classical setup is able to handle nondeterminism by treating the nondeterminism as given by an oracle, resulting in a deterministic computation. — Carl (CBM · talk) 20:51, 3 November 2015 (UTC)