Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why Halting problem is Recursively Enumerable?

, , No Comments
Problem Detail: 

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?

Asked By : Drupalist

Answered By : Ds D

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback