# 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) Commented Jan 29, 2015 at 22:30

## 1 Answer

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)

+If function g(x) be computable then the set B will be computable or in the other words it is decidable.