-1
$\begingroup$

I believe this is true and I have given a simple proof of this: If A is Turing-reducible to B then there exists a Turing machine with oracle for B that decides A, because B is Turing-recognizable then by using the oracle for B we can decide A and therefore A is Turing recognizable.

$\endgroup$
1
  • $\begingroup$ What's your question? We are a question-and-answer site, so we require you to articulate a specific question about your situation. What efforts have you made to answer your own question? If you have a proof, it would be appropriate to share the proof. We discourage "please check my answer" questions. $\endgroup$
    – D.W.
    Commented Jun 7, 2022 at 17:46

1 Answer 1

1
$\begingroup$

The statement is false. Consider the language $H$ of the halting problem and let $H'$ be its complement.

$H'$ is Turing reducible to $H$ and $H$ is recognizable, however $H'$ is not recognizable (if $H'$ were recognizable then $H$ would be decidable).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.