Is my logic here correct? Primitive recursion and diagonalization proof

266 Views Asked by At

I'm trying to understand diagonalization as it applies to proving that not all total functions are primitive recursive functions. For example, say that we enumerate all primitive recursive functions as $f_0, f_1, f_2, \dots$. Then, suppose that we show that $d(x) = f_x(x) + 1$ is not in this list (by diagonalization), and so it is not primitive recursive.

Does it then make sense to argue that $g(x) = f_x(x)$ is not primitive recursive either, because if it were, then $d(x) = g(x)+1$ would be primitive recursive as well (since the set of primitive recursive functions is closed under the successor function)?

1

There are 1 best solutions below

1
On BEST ANSWER

Yes. It makes sense to say that $d$ is not primitive recursive, for precisely the reason that you state.