1
$\begingroup$

Suppose $f(x,y)$ is a total computable function. For each $m$, let $g_m$ be the computable function given by $g_m(y) = f(m,y)$.

Construct a total computable function h such that for each $m$, $h \not= g_m$.

My work:

Is this a really simple question where I can just use the diagonal method?

Define

$ h(m,y) = \begin{cases} g_m(y)+1 & \mbox{if $g_m(y)$ is defined} \\ 0 & \mbox{ if $g_m(y)$ is undefined} \end{cases} $

Then clearly, $h$ differs from $g_m$ at all points. I'm just not entirely sure if $h$ as I constructed it is total and computable.

2 Answers 2

3

I agree it is a really simple question where you can just use the diagonal method.

Certainly $h$ is total and computable. $g_m(y)+1 = f(m,y)+1$ by definition, and $f$ is a total computable function. Moreover, your "if $g_m(y)$ is undefined" case is unnecessary: $g_m(y) = f(m,y)$ and so is never undefined.

However, I would guess that the question wants $h$ to be a function of one argument, not of two. Otherwise it does not really make sense to ask if it is the same function as $g_m(x)$ for some $m$. This is easy to fix, but since your question seems to be a homework problem I do not want to give away too much unless you ask me to.

(You should use the "homework" tag if your problem is homework.)

2

Define $h(m) = f(m,m) + 1 = g_m(m) + 1$

$h$ is a computable function since $f$ is a computable function.

$h \neq g_m$ for any $m$ since $h(m) = f(m,m) + 1 = g_m(m) + 1 \neq g_m(m)$.