[codeflo]

I think the more widespread term for what you call "computably countable" is "computably enumerable", perhaps in part to make the distinction more clear. For example, the set of all natural numbers is (trivially) c.e., but has many non-c.e. subsets. But to understand this is understanding the Entscheidungsproblem, so it shouldn't be surprising that this was less clear before that was resolved.

[ogogmad]

Computably countable is also a correct term. In line with this approach to computability theory: http://math.andrej.com/asset/data/synthetic-slides.pdf

It shows that the unsolvability of the halting problem follows from:

- The computable uncountability of N^N, which can be proved using an identical argument to the one Cantor used to prove the set-theoretic uncountability of N^N.

- The computable countability of the partial maps from N to N.

If the halting problem were solvable, then the second bullet point would contradict the first. So it's essentially a weird twist on set theory that uses constructive logic.

[codeflo]

I don't doubt that the term is in use, and I understood what you meant. But it's not listed among seven (!) synonyms for computably enumerable on Wikipedia, and more the point, the slides you linked to also don't contain that term.

However, that's not the point I wanted to make. I wouldn't like calling it computably countable even if everyone else did, simply because it gives the wrong intuition about subsets.

[ogogmad]

> the slides you linked to also don't contain that term

The term "countable" is used in the slides, where it means computably enumerable. The adjective "computably" is used when there's a need to distinguish set-theoretic notions from similarly behaved computability-theoretic notions. Otherwise the meaning of the term "countable" can be context-dependent.

> it gives the wrong intuition about subsets

In constructive logic, a countable set can contain an uncountable subset. The misleading intuition (in the context of non-classical logics) is based on classical logic where countability is a statement about the size of a set. Whether you think constructive logic is a good way of explaining computability theory is another question, but it's certainly a viable way of doing it.

It's like how the term "line" can mean something different in hyperbolic geometry from what it means in Euclidean geometry. You could argue that it might mislead people about the nature of parallel lines, but that's why hyperbolic geometry is not Euclidean geometry. Another example is using "multiplication" to refer to an operation on matrices, which might make people think that AB=BA when that usually isn't true. Mathematics is all about re-using terms and pointing out that there are differences.

[edit]

Admittedly, the slides do use the term "enumerable" as well, so that's another option. When there's a possibility for confusion with set theory, you can say "computably enumerable" as you suggested.

[edit] Made lots of edits. Hopefully, that's it.