Well-definedness of uncomputable functions.

Question

I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never had any doubt that things such as the busy beaver function were well-defined. Then I read this article where it was stated that two numbers described by uncomputable functions like BB might be incomparable within a certain system of axioms - it could be independent of the system which one was larger. This was taken to mean that one might not be larger than the other at all. I took this to suggest that even a simple uncomputable function like BB(n) could be undefined in a sense.

However, it seems to me that, given two numbers, it should always be possible to decide which is bigger. It also seems like the busy beaver function should be well-defined since it is making a precise statement about machines which could theoretically be implemented in the physical world.

So, are uncomputable functions well-defined in general? What characteristics would make one well-defined or not, and is there something I'm conceptually missing in the way that I am approaching these questions? Thank you for helping me understand!

Answer 1

The busy-beaver-function is well-defined because every halting turing machine can only write a finite number of ones on the tape, hence there must be a champion, and $bb(n)$ is the number of ones this champion writes down.

But the busy-beaver-function is not computable because we cannot determine which turing machines halt and which do not. This (and only this) prevents us from determining the busy-beaver-champion and therefore determining $bb(n)$ in general.

"Computable" means that there is an algorithm being able for every n to either determine $f(n)$ or determine that $f(n)$ is not defined.

"Well-defined" means that there is a description guaranteeing that for every $n$ there is either only one possible value $f(n)$ or that the function is not defined. (It is not necessary that this $f(n)$ can actually be determined , if $f(n)$ is defined.)

Answer 2

There are two things to separate. First, the definition of functions. A function $f:A\rightarrow B$ is a relation $f\subseteq A\times B$ which is both left-total and right-unique.

Second, the computability of a function. Here one generally considers (partial) functions $f:{\Bbb N}_0^k\rightarrow{\Bbb N}_0$. The question is whether there is an algorithm computing the function. By the thesis of Church, the computable functions are exactly those that are partially recursive.

Note that the number of computable functions is denumerable as they correspond to the set of C-programs and the set of C-programs (as words over the keyboard alphabet) is denumerable.