CODEWITHSUNDEEP
turing-machinescomputation
Ohad
Ohad

Reputation: 1647

How can I show reduction from every language in RE to HP

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..

Upvotes: 0

Views: 654

Answers (1)

Cactus
Cactus

Reputation: 27636

(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:

  1. If b∈L, then M[m(L)](b) halts with output TRUE
  2. b∉L and M[m(L)](b) halts with output FALSE
  3. b∉L and M[m(L)](b) diverges

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

  • If HP(m(L), b) returns TRUE, we know that M[m(L)](b) converges, so just run it and return whatever TRUE/FALSE answer it results in.
  • If HP(m(L), b) return s_FALSE_, we know that M[m(L)](b) diverges, which it is only allowed to do if b∉L (see case 3 above). So we then don't run M[m(L)](b); instead, we just output FALSE.

Thus, HP is RE-Complete

Q.E.D.

Upvotes: 2

Related Questions