2
$\begingroup$

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence:

The word problem for commutative semigroups is effectively decidable.

I know what a “decidable” problem or, more precisely, a “decidable” language over an alphabet means: there is an algorithm that terminates on every input and returns “yes” or “no”, depending on whether the input belongs to the language or not.

So, if the sentence were “The word problem for commutative semigroups is decidable”, I'd think this: for each (most likely, finite) alphabet $𝛴$ and each commutative semigroup $\langle G,\mathord\circ\rangle$, where $G\subseteq 𝛴^*$, there is an algorithm that, started with a string $s\in 𝛴^*$ as input, terminates and says whether $s\in G$ or not. Please correct me if I'm wrong.

Now, what the hell does effectively mean? Is there anything non-effectively decidable or ineffectively decidable? How would effectively decidable be different from ineffectively decidable or non-effectively decidable?

$\endgroup$
4
$\begingroup$

"Decidable" and "effectively decidable" mean the same thing. I realize that's a bit confusing; but it reflects a difference in terminology between two communities.

(Strictly speaking, I suspect there might be a difference between those two concepts if Church's thesis is false; but if Church's thesis is true, then they are equivalent.)

$\endgroup$
5
  • $\begingroup$ Which communities? $\endgroup$ Jun 18 at 15:30
  • $\begingroup$ @reinierpost, logic vs theoretical computer science $\endgroup$
    – D.W.
    Jun 18 at 17:14
  • $\begingroup$ Thanks. If you mean en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis, then, what's the relation between „effectively calculable“ and „effectively decidable“? $\endgroup$ Jun 19 at 23:27
  • $\begingroup$ @GeekestGeek, it seems described well in the link you provide. As a coarse approximation, you can take them as synonyms. If you want to be precise, then decidable has a precise mathematical definition, whereas "effectively calculable" does not; but the Church-Turing thesis (which is widely believed) suggests that we can treat them as equivalent. $\endgroup$
    – D.W.
    Jun 20 at 1:36
  • $\begingroup$ Thx! The links says a lot of stuff; as for the specific question, the text there merely confuses us rather than clarifies anything. I see „effectively decidable“ there only in parentheses. The reader is left to guess how the contents of the parentheses is connected to the stuff around it. Parentheses may mean lots of various things. If you say that the stuff in parentheses provides synonyms there, it's fine with me, though the cited text doesn't say this explicitly. And, after all, it's only a part of Wikipedia; I think any of us can change that page at any moment without peer review :-). $\endgroup$ Jun 20 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.