6

In "Introduction to Gödel's Theorems," the adverb "effectively" is almost ubiquitous: effectively enumerable, effectively decidable, effectively computable, etc.

Here are some sample quotes:

A property/relation is effectively decidable iff there is an algorithmic procedure...

<p>A numerical property or relation is effectively decidable iff its characteristic function is effectively computable.</p>

<p>A one-place total function $f:\Delta\rightarrow \Gamma$ is effectively computable iff there is an algorithm...</p>

<p>There is an effectively enumerable set of numbers $K$ such that is compliment $\bar{K}$ is not effectively ennumerable.</p>

<p>for a properly formalized syntax $\mathcal{L}$, there should be clear and objective procedures...for <em>effectively deciding</em> whether a putative constant-symbol really is a constant...</p>

Why can't one just state the feature or property without any modification?

Thanks

  • 4
    Please provide full sentences or a paragraph where this adverb appears. One must consider context if one wants to understand why the author may have chosen to use "effectively" frequently. You've posted to little information for anyone other than @PeterSmith to be able to answer your question. – amWhy Jun 23 '18 at 19:09
  • 9
    In general, "effectively" is used to indicate that something can be done in a computable manner (following the formal definition of computability). For example, every subset of $\mathbb{N}$ is enumerable, but only some are effectively enumerable. So the term "effectively" can be vital to convey the correct statement. More concrete examples from the text would be very helpful. – Carl Mummert Jun 23 '18 at 19:13
  • @peter.smith relevant to your interests – MJD Jun 24 '18 at 15:43
  • @Carl: Is that an effective way of explaining this terminological use? :) – Asaf Karagila Jun 24 '18 at 19:53

3 Answers3

9

In the context of "decidable" and "computable" I think "effectively" is just for emphasis -- it's a way to attempt to remind the reader that the claim is that such-and-such can be done by machine, or by mindless following of rules (once those rules have been appropriately constructed once and for all). In contrast to being doable by a sufficiently wise human mathematician.

But I don't know any relevant meaning of "decidable" and "computable" that doesn't already implicitly include this.

"Effectively enumerable" is a bit less empty, because some authors (working in other fields) may use "enumerable" as a synonym for "countable", whereas "effectively enumerable" unambiguously points to the kind of enumeration that is done by mindless processes. (This is more commonly known as "recursively enumerable", but that phrase is even less intuitively understandable, and will sound out of place before the argument that this has anything to do with recursion has been carried out).

hmakholm left over Monica
  • 286,031
  • 2
    Looking at his chapter 3, I agree it is mostly for emphasis, although he does not work with a formal model of computation, so "effectively" means "according to an algorithm" where algorithm is left as an informal concept. The content of the chapter is all completely standard material. – Carl Mummert Jun 23 '18 at 19:21
  • Perhaps he is informally using the word "effectively" to bring out a subtle but very important point. To give a specific example, Turing's Halting Problem proof says there is no single algorithm that can prove or disprove whether every program will halt. But that does not necessarily mean that there is no proof that every individual program will halt or not - the proofs may be different for different programs (and there may be an infinite number of such proofs), but no single proof can generalize all of them. – alephzero Jun 23 '18 at 19:52
  • 1
    @alephzero: Actually it does imply that, at least if "proof" means proof in a somewhat sane proof system. If all programs had proofs telling whether they halt or not, we could effectively decide the halting problem by searching for a proof of one or the other, in parallel. – hmakholm left over Monica Jun 23 '18 at 20:44
6

Henning, Bram and Carl are of course right that my "effectively" is mostly for emphasis, to highlight the kind of decision procedures, enumerations, axiomatisations etc. are in question.

We are, for example, concerned with what is effectively decidable -- i.e. decidable by a plodding finite step-by-step algorithmic procedure (so we want to emphasize that appeal to oracles, or to infinitary processes of hypercomputation, or anything exotic is like is ruled out as a "decision" procedure of the sort we care about).

We are, for example, concerned with what is effectively enumerable -- i.e. what can in effect by listed by a plodding finite step-by-step algorithmic procedure (so we want to emphasize that not any old function from numbers to widgets is enough to list the widgets in the way we are want to get at).

We are, for example, concerned with effectively axiomatized theories -- i.e. theories where it is effectively decidable what's an axiom (so we want to emphasize that not any old bunch of axioms will do for the sort of theories we are concerned with).

And so it goes. It could be that I overdid the repetitious use of "effectively". However -- without doing a careful re-read of the chapter -- my guess would be that it was indeed probably better to err on the side of being explicitly repetitious!

Peter Smith
  • 54,743
4

Turing's definition of computability can be seen as a formalisation of the more informal notion of an 'effective method', which at that time was understood to be an algorithm or step by step instructions that a human would be able to understand and perform. Thus, by adding the word 'effective', I am guessing that Peter Smith is emphasizing the fact that when he talks about computations and decision procedures, he talks about those kinds of computations, i.e. ones compatible with Turing's definition, as opposed to more exotic forms of computation like hypercomputations.

Bram28
  • 100,612
  • 6
  • 70
  • 118