1
$\begingroup$

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 $.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – chi Sep 21 '18 at 19:15
  • $\begingroup$ @chi Thanks, I have edited the answer. $\endgroup$ – xskxzr Sep 22 '18 at 5:37
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ thanks for your thoughts on this, I'm looking for a proof , do you have any possible explanation for why this is true $\endgroup$ – Mathew Sep 21 '18 at 7:21
  • 1
    $\begingroup$ Why is every subset of $\mathbb{Z}$ the range of some program? $\endgroup$ – xskxzr Sep 21 '18 at 16:00
  • $\begingroup$ Why not, we can always write such a program for any subset of Z $\endgroup$ – Komal Pathade Sep 21 '18 at 16:54
  • $\begingroup$ 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. $\endgroup$ – chi Sep 21 '18 at 19:09
  • $\begingroup$ 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. $\endgroup$ – chi Sep 21 '18 at 19:13

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.