1

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?

Dávid Natingga
  • 2,889
  • 2
  • 27
  • 41
  • 2
    You can use the same method as in this answer: http://math.stackexchange.com/questions/873063/uncomputability-of-subset-relation/874662#874662 . Start by proving that there is no computable function $G$ that, given an oracle for an arbitrary function $f\colon \mathbb{N}\to\mathbb{N}$, determines whether the range of $f$ is infinite. – Carl Mummert Jul 25 '14 at 19:41
  • 4
    For questions like this, there's a wonderful result called Rice's Theorem. It says that a set of the form ${e:\text{something about }W_e}$ is never recursive unless it's all of $\mathbb N$ or empty. – Andreas Blass Jul 25 '14 at 20:54
  • What does $#$ mean? What does $#W_e$ or $#\mathbb{N}$ mean? – user150396 Jul 25 '14 at 23:51
  • 1
    For a direct proof, suppose your set is computable. Then to know if $\Phi_e(e)$ halts, you can just create $e'$ so that $\Phi_{e'}(n) = \Phi_e(e)$ on every $n$. It follows that $e'$ is in your set iff $\Phi_e(e)$ halts. Therefore the halting problem would be computable, and we know it is not. – Archimondain Jul 26 '14 at 00:20
  • @user150396 $#A$ denotes the cardinality of a set $A$. – Dávid Natingga Jul 26 '14 at 08:06
  • Thanks to you all for your answers. – Dávid Natingga Jul 27 '14 at 19:32

0 Answers0