Comment by j2kun

I think you are missing some basic concepts here. There is a single Turing machine (of constant size) which, when given any integer n, outputs A(n). This is the statement that A(n) is computable. One can prove that there is no such Turing machine for the function BB(n) or any function f(n) that bounds BB(n). Such a function would be used to solve the Halting problem as follows: given a TM M and a string x, compute k = f(|M|) and run the TM on x for k steps. If the simulation halts within k steps, output "halt" and otherwise output "loops forever."

Your example of foo/bar(x) is not quite correct. If you fix a program bar, then it is not necessarily impossible to characterize (and hence compute) the set of strings for which bar(x) halts. This is not the statement of the Halting problem, and as far as I know there is no theorem that says such a function "bar" exists.