I would like to prove that the following subset is outside both RE and coRE:

$$A = \{ (p, (d_1, d_2,\dots, d_k)) \mid \text{for each } 1 \le i,j \le k, \; [p]d_i = [p]d_j \}, $$

where $p$ is a program, $d_i$ are inputs, and $[p]d$ is the result of running $p$ on the input $d$.

I was thinking about creating a mapping reduction from HALTnil (the halting problem for the empty input) to $A$ and from the complement of HALTnil to $A$ as well.

Since HALTnil does not belong to coRE, neither does $A$. Since the complement of HALTnil does not belong to RE, neither does $A$.

Can someone suggest an approach that covers it?

  • 3
    $\begingroup$ I suggest spending a few more hours on the problem. This is the only way to learn. $\endgroup$ – Yuval Filmus Oct 5 '19 at 19:16
  • $\begingroup$ Try playing around with programs a bit. Given program $q$, build program $p$ such that on input $0$ it runs $q$ on empty input, while on other inputs does something else (try several possibilities). $\endgroup$ – chi Oct 7 '19 at 12:08
  • $\begingroup$ Thank you both, I came up with the following idea: the reduction function gets program q and returns program p. 0 nil^1 nil^2... nil^k-1: read input, if input == 0 run q on empty input, else return constant value, note that if p stops on empty input, I am also adding in program q to return the a constant value. $\endgroup$ – Tom.A Oct 8 '19 at 16:43

Your Answer

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

Browse other questions tagged or ask your own question.