0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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) $\endgroup$
    – Ran G.
    Commented Jan 29, 2015 at 22:30

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.