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.

This is from an exercise in Boolos' Computability text. My problem is as follows:

I am looking for a method that encode numbers for recursive functions. Then given such an encoding for recursive functions by natural numbers, let d(x) = 1 if the one-place recursive function with encoding number x is defined and has value 0 for argument x, and d(x) = 0 otherwise. Show that this function is not recursive.

I am thinking the actual question is just a diagonalization argument, and it doesn't depend in any way on details of the coding.

share|improve this question
    
It is indeed just a diagonalisation argument, and it doesn't depend on the details of the enumeration at all – just that it can be done. –  Zhen Lin May 5 '12 at 16:58
    
Boolos has already set up the argument for you. It's a proof by contradiction: suppose $d$ is recursive. Then it has a number, etc. –  Zhen Lin May 5 '12 at 17:00
    
So the coding scheme is: Let d(x) = 1 if the one-place recursive function with code number x is defined and has value 0 for argument x, and d(x) = 0 otherwise ? How do I get that d is not recursive from this? I'm not seeing it. –  Quaternary May 5 '12 at 17:02
    
No, that's not the coding scheme, and as I said, the coding scheme doesn't matter if all you want is to solve the exercise. (In other words, you're asking two separate questions here.) –  Zhen Lin May 5 '12 at 18:32

1 Answer 1

up vote 1 down vote accepted

The subject of enumerating the recursive functions in a reasonable way is rather sophisticated. However, it is easy to see that the set of all recursive functions $\mathbb{N} \rightharpoondown \mathbb{N}$ must be a countable set, so there is some surjection from $\mathbb{N}$ to the set of all recursive functions.

Fix one such surjection, and let $d$ be the function as described by Boolos. Suppose $d$ is recursive; then it has a number, say $x$. What is $d (x)$? If it's $0$, then that by definition of $d (x)$ we must have $d(x) = 1$ – contradiction. If it's not $0$, then that means $d (x) = 0$ – contradiction. If it's not defined, then that means $d (x) = 0$ – contradiction. So $d$ can't be recursive.

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.