I See on Our Lecture note on Theory of Computation Course that:

.... The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. ....

it's conclude that:

F be a Computable Function. Predicate $\exists x( F(x)=y)$ is also computable.

everyone would help me and tutor some definition, why the above sentence is correct?

I think if this predicate is false, our Algorithm is not terminated and so $\exists x( F(x)=y)$ is not computable. my conclusion is right?

  • $\begingroup$ i think, it we start from 1 we can choose an appropriate value for x, and so in this state, it's computable. $\endgroup$
    – user153695
    Aug 8, 2014 at 11:35
  • $\begingroup$ Dear @user153695, if the predicate is false? what's about this? $\endgroup$ Aug 8, 2014 at 11:36

1 Answer 1


The statement is not correct. For each Turing machine $T$ and input $n$, we can compute a computable function $F$ such that $F(x)=y$ if and only if $T$ halts in $x$ steps on input $n$. Thus if $\exists x, F(x) = y$ were computable we would be able to solve the halting problem.


Your Answer

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

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