[ogogmad]

I need to find a reference for this:

Goedel apparently believed that it was impossible to explicitly enumerate all the partial computable functions over the integers, until Turing proved him wrong. He reasoned as follows:

- You can't enumerate the total functions because Cantor's diagonal argument is constructive. Given a claimed enumeration of N^N, you can perform Cantor's diagonal construction to produce a computable element of N^N not in the enumeration. So N^N is computably uncountable.

- Classical set theory says that a superset of an uncountable set is also uncountable.

The problem is that while a superset of an uncountable set is uncountable, a superset of a computably uncountable set may instead be computably countable. The partial functions over the integers show that this is indeed the case.

Cantor's construction is blocked because a partial function can output a degenerate value called non-termination. A computable function must map the non-termination value to itself. Since it isn't mapped to something different, Cantor's construction can't produce something outside an enumeration.

[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.

[bsedlm]

> The problem is that while a superset of an uncountable set is uncountable, a superset of a computably uncountable set may instead be computably countable. The partial functions over the integers show that this is indeed the case.

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

Can anybody give an example?

does this have any to do with rationals? or is it more related to limits and calculus?

[ogogmad]

> does this have any to do with rationals? or is it more related to limits and calculus?

No.

I'm going to use Haskell, which I'm going to assume you know. I'm using it because it seems closer to the math. The type for naturals is:

data Nat = Zero | Succ Nat

and then all Haskell functions of type `Nat -> Nat` represent partial functions. They're not total functions because they might enter an infinite loop for some inputs. You can clearly enumerate all Haskell functions which are syntactically correct and which have type Nat->Nat, so the partial functions of that type are computably enumerable.

But consider the total functions of type Nat->Nat (i.e. those that never enter an infinite loop). Assume you can have a function `en :: Nat -> (Nat -> Nat)` which can output every total function of type Nat->Nat.

Then the function `counterexample n = Succ (en n n)` is a function that cannot be outputted by `en`, and therefore `en` fails to enumerate all total functions.

I've got other things to do, unfortunately, so I can't say more than this.

[edit] Fixed the counterexample.

[bsedlm]

> You can clearly enumerate all Haskell functions which are syntactically correct and which have type Nat->Nat

Is this a finite process?