[karatinversion]

To tie this back to TFA, even before we knew that the Halting problem was uncomputable, we could have defined

  f(n) = { 1 if there is a Turing machine with at most n states that solves the Halting problem;
           0 otherwise }

and we can easily show that f(n) is computable without proving that the Halting problem is undecideable. Viz., f is either constant 0; or equal to a function of the form

  g_k(n) = { 1 if n >= k;
             0 if n < k },

and both the constant 0 function, and all the g_k functions, are computable; thus f is computable.