Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?

88 Views Asked by At

Denote every partial computable function $f$ with its Godel number $e \in \mathbb{N}$ by $\phi_e$. Then let the halting set of $\phi_e$ be $W_e=\{x \in \mathbb{N} | \phi_e(x) \downarrow \}$ where $f(x)\downarrow$ means that $f$ halts on the input $x$. Define a set $E=\{ e \in \mathbb{N} | \#W_e = \#\mathbb{N}\}$.

Is $E$ computable?

Intuitively, $E$ is not computable since we would need to check that $\phi_e$ halts or does not halt on infinitely many inputs, but we require our proof to be finite. However, how could I prove it? Also, is there any way to convert the intuition directly into the proof that $E$ is not computable rather than constructing a tricky function and then derive a contradiction?