# Deciding whether $f(x) = f(y)$ is beyond RE and coRE

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?

• I suggest spending a few more hours on the problem. This is the only way to learn. – Yuval Filmus Oct 5 '19 at 19:16
• 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). – chi Oct 7 '19 at 12:08
• 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. – Tom.A Oct 8 '19 at 16:43