Proving non-recursiveness

111 Views Asked by At

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.