A problem about computability theory

  • Context: Graduate 
  • Thread starter Thread starter iamwanli
  • Start date Start date
  • Tags Tags
    Theory
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
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
 
Physics news on Phys.org
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: