Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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