# Is the following function computable? is it total?

I have the following function:

$$f : N \to N$$ and $$f(n)= \max_{i \leq w(n)} g_{i}(n)$$
with $$g_1, g_2,...g_{w(n)}$$ being an enumeration of all computable functions $$g_i$$, and $$w : N \to N$$ being any non-decreasing function.

Please correct me if I am wrong:

1. I don't think this is computable as the enumeration of all total computable functions is enumerable.

2. I am not sure if the function is total as the max element is not defined.
Nothing ensures that we have this maximal element, given that the "set" of all total computable functions is infinite hence again nothing ensures that we have this maximal element.
Not like it is with ordered sets for example where this is ensured via Zorns lemma.
Or am I missing something and it doesn't really matter if we know that this maximal element exists (or do we actually know that this maximal element must exist?), and merely by definition is this function total?

• Is $w$ computable? If $w$ is not computable, then $f$ is unlikely to be computable. Jan 13, 2022 at 9:25
• Suppose $n=1$, $w(1)=100$ and $g_{100}(1)$ is not defined, i.e., the Turning machine that compute $g_{100}(1)$ loops forever. What is the meaning of $\max_{i\le w(1)}g_i(1)$? Undefined? Jan 13, 2022 at 9:28

Your function is well-defined, that is, total. The value of $$f(n)$$ is the maximum of the finite set $$\{g_1(n), \ldots, g_{w(n)}(n)\}$$. The maximum of a finite set of numbers always exists.
Your function is computable iff $$w$$ is bounded. Suppose first that $$w$$ is not bounded, and assume for the sake of contradiction that $$f$$ were computable. Then $$h(n) = f(n) + 1$$ would also be computable. Therefore $$h = g_i$$ for some $$i$$. Since $$w$$ is unbounded, we can find $$n$$ such that $$w(n) \geq i$$. Therefore $$f(n) \geq g_i(n) = h(n) = f(n) + 1$$, which is impossible.
Suppose next that $$w$$ is bounded, say $$\max_n w(n) = M$$, and let $$m$$ be the minimal value such that $$w(m) = M$$. We can compute $$f(n)$$ as follows: if $$n < m$$ then we output the hardcoded value $$f(n)$$, and otherwise we output $$\max(g_1(n),\ldots,g_M(n))$$.
• I don't understand your question. The function $w$ maps natural numbers to natural numbers. So $w(n)$ is some natural number. Your set contains at most $w(n)$ numbers. For example, if $w(10) = 100$, then for $n = 10$, your set contains at most 100 numbers. Jan 13, 2022 at 7:33