To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.:

we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it...

In general, for proving a set is r.e. , we must recognize every element IN the set? How do we deal with functions like f(x)= 1 if x is in K and 0 if x is not in K? is f computable?

  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Apr 4 '18 at 0:27
  • $\begingroup$ before i edit though, is it right? $\endgroup$ – user352102 Apr 4 '18 at 0:31
  • $\begingroup$ "for proving a set is r.e. , we must recognize every element IN the set?" - the way to answer this is to check the definition of r.e. Have you tried that? $\endgroup$ – D.W. Apr 4 '18 at 0:38
  • $\begingroup$ I believe I am right then. $\endgroup$ – user352102 Apr 4 '18 at 0:44
  • $\begingroup$ Your proof is correct. Why do you need to deal with such $f$? $\endgroup$ – xskxzr Apr 4 '18 at 2:42

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.