The Question: I found this claim in Douglas Hofstadter's book 'Gödel, Escher, Bach'. The author says that this result was proven by Church and Kleene. Correct me if I am wrong, but I interpret this claim as saying that there is no algorithm that can name all countable ordinals.
I am mystified why this should be so. Any intuitive explanation or reference to this result will be much appreciated. In particular, has this problem of naming ordinals been shown equivalent to some uncomputable problem like the halting problem or some other uncomputable problem in the Turing universe? I have some familiarity to computability theory at the level of Barry Cooper's book, if that helps in explaination.
What I tried: With the help of Conway's 'The book of numbers', I know how the ordinals are counted till some extent. I will try to extend the counting a little.
$$1,2,3,...,\omega,..., \omega +1,..., \omega .2,..., \omega^2,...,\omega^{\omega^{\omega^....}}\equiv \epsilon_0,...,\epsilon_0 +1,...,\epsilon_0+\omega,...,\epsilon_0.2,...,\epsilon_0.\omega,...,\epsilon_0^{\epsilon_0},...,\epsilon_0^{\epsilon_0}+1,...,\epsilon_0^{\epsilon_0}.\epsilon_0 = \epsilon_0^{\epsilon_0+1}\equiv\epsilon_1,...,\epsilon_0^{\epsilon_0+\epsilon_0}\equiv \epsilon_{\epsilon_0},...,\epsilon_0^{\epsilon_0 + \epsilon_0^{\epsilon_0+\epsilon_0}}\equiv \epsilon_{\epsilon_{\epsilon_0}},..., \epsilon_{\epsilon_{\epsilon_{...}}}\equiv \alpha,...$$
The book does not mention how to proceed after this, but I will try to do it.
$$,...,\alpha+1,...,\alpha+\omega,..., \alpha+\epsilon_0,...,\alpha .2,...,\alpha.\omega,...,\alpha.\epsilon_0,...,\alpha^2,...,{\alpha}_{\alpha+1}={\alpha}_{\alpha}.\alpha\equiv\alpha[1],...,{\alpha}_{{\alpha}+2}={\alpha}_{\alpha}.{\alpha}^2\equiv \alpha[2],...,{\alpha}_{{{\alpha}+{\alpha}}_{{\alpha}+1}}\equiv \alpha[\alpha[1]],...,\alpha[\alpha[\alpha[...]]]\equiv \beta,...$$
Here, I have introduced the notation $\alpha[1]$ because the subscript and superscript notation has already been used, and cannot be used again without introducing ambiguity.
Is my extension of the notation after $\alpha$ correct?
I can understand that there are subtleties with extending this notation system, and we have to introduce new notations at each step. Does the algorithmic difficulty lie in coming up with new symbols and notations every time we run out of symbols for our system? But we can always have a Turing machine which randomly generates new symbols from a n x n pixel grid, and increases the value of n whenever all the possibilities are exhausted for that value of n. But the subtlety here is that such n x n grid can generate less symbols less than $\omega$, the first infinite ordinal.