1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.