# Computable Function and Predicate Question

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?

• i think, it we start from 1 we can choose an appropriate value for x, and so in this state, it's computable. Aug 8, 2014 at 11:35
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.