When thinking about diagonalization, I’ve always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter?
Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn’t exist, or the diagonal gives an uncomputable number?
Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?
Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable? Something seems wrong here.
In general, what are the catches when doing diagonalization pertaining to computability?