let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false. In both cases for a program to be in S or M it must halt.
Consider programs P in S, I will say the integer n is "in" P if there is some integer m such that P(m)=n
Consider a program P in M, I will say the integer n is "in" P if P(n)=true
Consider 2 programs P1 in S and P2 in M. I will say P1 and P2 are equivalent if for each integer n in P1, n is also in P2 and for each integer n in P2, n is also in P1.
I believe I have managed to prove the following:
There doesn't exist a program P such that P takes as input a program in S and returns an equivalent program in M.
However what I'd actually like to know is if for each program in S there is an equivalent program in M.
I figure this question can be answered in one of two ways. An explicit function in S could be given such that it has no equivalent function in M (this would require a proof that there is no equivalent function in M). Or it must be proven that for each program in S there is an equivalent program in M.
If there is another way to resolve this question other than one of the two ways I mentioned above I'd be interested to hear it. Also if you feel that simply proving there is no function P such that P takes inputs from S and returns equivalent programs in M is sufficient, please give an argument as to why this is.
I have chosen not to include the proof I mentioned above as its not strictly essential to the question however you think it would be relavent let me know and I can include it.
If any clarifications need to be made let me know.
Also please note that I might have gotten the tags wrong, I'm fairly new to the CS stack exchange, if I should change them let me know.