does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

Question

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.

Thanks

Answer 1

Let us denote by $L_S(P)$ the set of numbers in $P$ for $P \in S$, and similarly by $L_M(P)$ the set of numbers in $P$ for $P \in M$.

Consider the following program $P \in S$. It interprets as input as a pair of integers $(x,y)$, runs the $x$'th Turing machine on the empty input for $y$ steps, returns $x$ if the machine halts, and returns some fixed $C$ if $x$ doesn't halt, where $C$ is the index of a halting Turing machine. Thus $L_S(P)$ is the set of indices of Turing machines which halt on the empty input. It is well-known that this language cannot be computed by an $M$-program, that is, $L_S(P) \neq L_M(Q)$ for all $Q \in M$.

More generally, a non-empty language is of the form $L_S(P)$ iff it is r.e., whereas a language is of the form $L_M(Q)$ iff it is recursive.