# 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) 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)