# Why Halting problem is Recursively Enumerable?

If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79)

$Definition.$The set $B\subseteq N$ is called r.e. if there is partially computable function $g(x)$ such that

$B = \{x \in N | g(x) \downarrow\}$

Halting problem is set of $(x,y)$ which program with number $y$ halts on $x$, I really can't understand when there is no program for Halting problem then what $g(x)$ is going to be applied for it?

• because you can just run the program $y$ on $x$ and wait until it halts (maybe you'll wait forever, which is why it is RE but not R) – Ran G. Jan 29 '15 at 22:30

If you want to understand Halting Problem is r.e. by Davis Book notation and you are looking for g(x) you can think of universal program! universal program is the function $\phi (x,y)$ that is the program which run program number $y$ on input $x$. This program is equal to partially computable function g(x) (see page 30 definition of partially computable). As Ran G mentioned, it is possible program y on input x never halt! That's the reason it is partial function not computable function(i.e. it is both partial and total)