- #1
nomadreid
Gold Member
- 1,707
- 222
- TL;DR Summary
- Wikipedia characterizes a recursively enumerable set at the top of its eponymous article with a statement that it seems to contradict at the end of the article. Or am I missing something?
In https://en.wikipedia.org/wiki/Recursively_enumerable_set, in the introductory section one reads
"...a set S of natural numbers is called recursively enumerable... if: ...There is an algorithm that enumerates the members of S."
and in a later section it says
"According to the Church-Turing thesis, ... thus a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom."
The only clue that I can see that would allow both statements to be valid would be the addition of "and only if" to the second statement. But the sense of "if" in a definition is supposed to be "if and only if", no?
True, the article does give a couple of other definitions that are more satisfactory, but I still wonder whether I am missing something essential here, or whether the introductory paragraph was just being a little sloppy. ?
"...a set S of natural numbers is called recursively enumerable... if: ...There is an algorithm that enumerates the members of S."
and in a later section it says
"According to the Church-Turing thesis, ... thus a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom."
The only clue that I can see that would allow both statements to be valid would be the addition of "and only if" to the second statement. But the sense of "if" in a definition is supposed to be "if and only if", no?
True, the article does give a couple of other definitions that are more satisfactory, but I still wonder whether I am missing something essential here, or whether the introductory paragraph was just being a little sloppy. ?