# Does intersecting the output of 2 programs give the output of another program?

Let $$S$$ be the set of all programs that take integers as input and return integers as output and halt on all inputs. Does there exist a pair of program in $$S$$, call them $$P_1$$ and $$P_2$$, such that there exists no program $$P_3$$ in $$S$$ for which the following hold for every integer $$y$$:

$$P_3(x)=y$$ for some $$x$$ iff $$P_1(x_1)=y=P_2(x_2)$$ for some $$x_1$$ and $$x_2$$.

Let $$f$$ be a computable bijection from $$\mathbb{N}^*$$ to $$\mathbb{Z}$$. For example, $$f(1)=0,f(2)=1,f(3)=-1,f(4)=2,\ldots$$

Note a non-empty subset of $$\mathbb{Z}$$ is the range of a program if and only if it is recursively enumerable. On the one hand, the range of a program $$P$$ can be enumerated by running $$P(f(1)),P(f(2)),P(f(3)),\ldots$$ On the other hand, for a non-empty recursively enumerable subset $$X$$ of $$\mathbb{Z}$$, there exists an enumerator $$E$$ that enumerates $$X$$. Suppose $$E$$ requires $$n$$ steps to output the first number, we can define a program $$P$$ that $$P(i)$$ returns the last number outputted by $$E$$ within at most $$\max\{n,f^{-1}(i)\}$$ steps.

Since the intersection of two recursively enumerable sets is still recursively enumerable, your $$P_3$$ exists if and only if the intersection is not empty.

• This is correct, but: 1) your S is not the same S as in the OP, and 2) the OP requested $P_3 \in S$, and you did not prove it halts on all inputs. Indeed, it can not do so when the two ranges are disjoint. The correct answer should be, I think, $P_3$ exists iff the two ranges intersect. (+1 anyway) – chi Sep 21 '18 at 19:15
• @chi Thanks, I have edited the answer. – xskxzr Sep 22 '18 at 5:37

No, such a pair of programs does not exist. In other words, a $$P_3$$ always exists.

On input $$x$$ just compute $$P_1(x)$$ and $$P_2(x)$$. Because both programs halt on all inputs (by their definition), these two computations will stop and provide two results. Then $$P_3$$ just compares these two results and iff they are equal outputs the result.

Your "programs" are the recursive funtions, and these are known to be closed under intersection.

I think as long as $$(P1\ range) \cap (P2\ range)$$ is non-empty, their will always be a function p3 in S that has $$(P1\ range) \cap (P2\ range)$$ as its range. (range is set of all output values for function)

Proof argument goes like this:

Given:

1. $$(P1\ range) \cap (P2\ range)\not= \phi$$

2. $$S$$ is the set of all programs that take integers as input and return integers as output this means: for any subset of integers $$I\subseteq Z$$, there exists a program $$P \in S$$ such that $$P:Z\mapsto I$$ (this is important inference from definition of S)

Since $$(P1\ range) \cap (P2\ range)\subseteq Z$$,

we conclude from 1 and 2 there exists $$p3\in S$$,

$$p3:Z\mapsto (P1\ range) \cap (P2\ range)$$

I hope this is clear

• thanks for your thoughts on this, I'm looking for a proof , do you have any possible explanation for why this is true – Mathew Sep 21 '18 at 7:21
• Why is every subset of $\mathbb{Z}$ the range of some program? – xskxzr Sep 21 '18 at 16:00
• Why not, we can always write such a program for any subset of Z – Komal Pathade Sep 21 '18 at 16:54
• We have only countably many programs, while the subsets of $Z$ are not countable. We won't be able to have any $I\subseteq Z$ as range, but only RE sets. Fortunately, the intersection of two ranges (two RE sets) is RE. – chi Sep 21 '18 at 19:09
• Your answer also suggests that, if the two ranges are disjoint, then $P_3$ can not exist since $P_3(0)$ would halt (since we require $P_3\in S$) returning an element in the intersection, which can not exist. – chi Sep 21 '18 at 19:13