A problem about computability theory

  • Level: Graduate 
  • Thread starter iamwanli
  • Start date
  • Tags Tags
    Theory
1 reply · 2K views · last reply
iamwanli
Messages
2
Reaction score
0
Soppose that A,B are effectively inseparable,B is r.e,then how to prove that [tex]\bar{A}[/tex] is productive
 
This isn't the place for homework. Also, when posting homework-type questions, you should state your definitions and what you've tried so far, rather than hoping that people will just give you an answer. Proper spelling and grammar wouldn't hurt either.

Anyways, what you've been asked to prove is false. Suppose [itex]B[/itex] is r.e. but not recursive. If the above were true, then we could apply it taking [itex]A = \bar{B}[/itex]. Then [itex]A[/itex] and [itex]B[/itex] are effectively inseparable because [itex]B[/itex] is not recursive, so the hypotheses are satisfied. But the conclusion, that [itex]\bar{A} = B[/itex] is productive must be false, since [itex]B[/itex] is r.e.
 
Last edited: