0
$\begingroup$

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?

$\endgroup$
2
  • $\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$
    – Maria Mohammadi
    Aug 8, 2014 at 11:36

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .