I ran into trouble with question 6.9 from Logic and Computability by Boole.

Let h(x, y) = 1 if the one-place recursive function with code number x is defined for argument y, and h(x, y) = 0 otherwise. Show that this function is not recursive.

As a side note, a previous problem asked for a way to code recursive functions by natural numbers. This coding is referred to by 'code number x'.

I found a hint on the internet, which advises to use the fact that there exists a recursive function f(x) such that f(0) = 0, but f(x) is undefined for x > 0. Since this function is recursive, there must be some code for it, call it a. How do I proceed? Perhaps by showing that h(a, y) is not effectively computable? Thanks in advance.

  • 1
    $\begingroup$ Assume $h$ is recursive and seek a contradiction. Try using $h$ together with $f$ (or functions similar to $f$) to obtain a new partial recursive function (with its own code $x$) that somehow conflicts with the definition of $h$. $\endgroup$ – realdonaldtrump Nov 6 '18 at 17:16

Your Answer

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

Browse other questions tagged or ask your own question.