Why is computable function in $\Delta_{1}^0$? I am not sure why computable functions are in $\Delta_{1}^0$. Can anyone explain this?
 A: Suppose that $S$ is a set of positive integers, or items which can be coded as positive integers.  One definition of $\Sigma_1^0$ is that it is the set of all sets $S$ expressible in the form
$$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$
A set $S$ is in $\Pi_1^0$ iff its complement, $S^C$, is in $\Sigma_1^0$, and $\Delta_1^0=\Sigma_1^0 \cap \Pi_1^0$.  So, a set $S$ will be in $\Delta_1^0$ iff both $S$ and $S^C$ are in $\Sigma_1^0$.  
If membership in $S$ is decidable, then there is a Turing machine $M$ which decides in a finite number of steps whether or not any given $x$ is in $S$.  Then
$$S=\{x\mid (\exists y)P_M(x,y)\},$$
where $y$ records a possible computation of $M$, and $P_M$ checks to see whether $y$ is a record of a legal computation of $M$ which starts from the input $x$ and ends at an accepting state.  Since checking to see whether something records a legal Turing machine computation or not is simple, $P_M$ is primitive recursive.  So, $S\in \Sigma_1^0$.  However, also,
$$S^C=\{x\mid (\exists y)P'_M(x,y)\},$$
where $P'_M$ now checks to see whether $y$ is a record of a legal computation of $M$ which starts at $x$ and ends in a rejecting state.  $P'_M$ is primitive recursive for the same reason that $P_M$ was, so $S^C\in \Sigma_1^0$.  Therefore $S\in \Delta_1^0$.
You can also prove that if $S\in \Delta_1^0$, then $S$ is decidable, so being $\Delta_1^0$ is equivalent to being decidable.  To see this, suppose that $S\in \Delta_1^0=\Sigma_1^0\cap \Pi_1^0$.  Then
$$
S=\{x\mid (\exists y_1)\cdots (\exists y_r) P(x,y_1,\ldots,y_r)\}
$$
and
$$
S^C=\{x\mid (\exists y_1)\cdots (\exists y_s) Q(x,y_1,\ldots,y_s)\}
$$
for some $r$ and $s$ and primitive recursive $P$ and $Q$.  To construct a Turing machine $M$ deciding whether or not $x$ is in $S$, let $M$ successively construct each possible sequence $(y_1,\ldots,y_{\max(r,s)})$ and then test $(x,y_1,\ldots,y_r)$ with $P$, halting and accepting on success, and $(x,y_1,\ldots,y_s)$ with $Q$, halting and rejecting on success.  Since one of these tests must eventually succeed, $M$ will always halt.
If $S$ is the graph of a computable function, then membership in $S$ is decidable as given any $(x,y)$, you can compute $f(x)$ and then accept $(x,y)$ if $y=f(x)$ and reject it otherwise.  So, $S\in \Delta_1^0$ in this case as well.
Proving that a decidable set $S$ was in $\Delta_1^0$ depended on the fact that $M$ was always guaranteed to halt regardless of whether $x\in S$ or not.  If $M$ only halted when it accepted, and otherwise might run forever, you would only have $S\in \Sigma_1^0$.  Just as being decidable characterized the $\Delta_1^0$ sets, the property of being semi-decidable in this way characterizes the $\Sigma_1^0$ sets, which are also called "recursively enumerable".
