L is considered to be Hard-RE if for every L' in RE, there is a reduction from L' to L (L'<=L) L is considered to be Complete-RE if L id Hard-RE and also L is in RE.
How can I prove that HP is complete-RE? i will need to show reduction from every language in RE to HP..
(Assuming RE means recursively enumerable and HP means the halting problem)
HP is trivially in RE
Consider the Turing machine that, given the description a of a Turing machine M[a] and some input b, just simulates running M[a] wiht input b until it halts; and when it does, it outputs TRUE. This machine will output TRUE iff M[a] halts for b, and will diverge when M[a] diverges; so it is a partial decider for the halting problem.
HP is RE-Hard
That is, given a language L in RE, it is reducable to HP: since L is in RE, there exists a Turing machine M[m(L)] such that for any input b, M[m(L)](b) will do one of the following:
So how do we turn that into a proper decider for L, given HP? Easy peasy! Just run your HP oracle on (m(L), b)!
Thus, HP is RE-Complete
Q.E.D.