1
$\begingroup$

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?

Thanks a lot in advance

$\endgroup$
2
  • $\begingroup$ Is $w$ computable? If $w$ is not computable, then $f$ is unlikely to be computable. $\endgroup$
    – John L.
    Jan 13 at 9:25
  • $\begingroup$ 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? $\endgroup$
    – John L.
    Jan 13 at 9:28
4
$\begingroup$

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))$.

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your response, however how is my value f(n) a maximum of the finite set {g_1(n),...,g_{w_{n}}? How is that a finite set of numbers when I have infinitely many computable functions to iterate over? Better said is it a finite set of numbers iff w is bounded otherwise it isn't? $\endgroup$
    – Joey
    Jan 13 at 7:30
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 13 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.