Is there a set A such that it's not recursively enumerable and not(K'≤ A) ?
where K' is complement of K= {n| φ n (n) halts}


  • $\begingroup$ What does it mean by $\le A$? Do you mean $\subseteq A$? $\endgroup$ – John L. Dec 24 '18 at 19:07
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – John L. Dec 24 '18 at 19:08
  • $\begingroup$ if K is ≤ than A it means that A is harder than K. it refers to reduction. @Apass.Jack $\endgroup$ – Rapuli Dec 24 '18 at 19:11
  • $\begingroup$ Thanks for the clarification. Please add it to the question. Also, please define what you mean by not$(K'\le A)$. Explain what you mean by $\phi_n$. All readers are not using the same textbook or the same notations as you, even if they are in the same country as you. In fact, many (a majority?) of them are in a different country. $\endgroup$ – John L. Dec 24 '18 at 19:20
  • $\begingroup$ if you are familiar with the context, the notation is obvious. $\endgroup$ – Rapuli Dec 26 '18 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.